http://www.ifac-papersonline.net/ en Copyright 09:26 AM Sunday 19, 2013 IFAC-PapersOnline http://www.ifacpapersonline.com 09:26 AM Sunday 19, 2013 09:26 AM Sunday 19, 2013 ET webmaster@ifac-papersonline.net webmaster@ifac-papersonline.net http://www.ifac-papersonline.net/Detailed/53497.html 04:00 PM Wednesday 31, 1969 http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53499.html 04:00 PM Wednesday 31, 1969 http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53501.html 04:00 PM Wednesday 31, 1969 http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53503.html 04:00 PM Wednesday 31, 1969 http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53505.html 04:00 PM Wednesday 31, 1969 http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53507.html 04:00 PM Wednesday 31, 1969 http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53509.html 04:00 PM Wednesday 31, 1969 http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53511.html 04:00 PM Wednesday 31, 1969 http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53513.html 04:00 PM Wednesday 31, 1969 http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53515.html 04:00 PM Wednesday 31, 1969 http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53517.html 04:00 PM Wednesday 31, 1969 A graph is well-indumatched if all its maximal induced matchings are of the~same size. We first prove that recognizing the class WIM of well-indumatched graphs is a co-NP-complete roblem even for (2P_5, K_{1, 5})-free graphs. We then show that the well-known decision problems such as Independent Dominating Set, Independent Set, and Dominating Set are NP-complete for well-indumatched graphs. We also show that WIM is a co-indumatching hereditary class and characterize well-indumatched graphs in terms of forbidden co-indumatching subgraphs. However, we prove that recognizing co-indumatching subgraphs is an NP-complete problem. A graph G is perfectly well-indumatched if every induced subgraph of G is well-indumatched. We characterize the class of perfectly well-indumatched graphs in terms of forbidden induced subgraphs. Finally, we show that both Independent Dominating Set and Independent Set can be solved in polynomial time for perfectly well-indumatched graphs, even in their weighted versions, but Dominating Set is still NP-complete. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53519.html 04:00 PM Wednesday 31, 1969 In this paper, we consider a problem of VLSI (very large scale integrated) design occurring in the routing phase. The problem is to determine the optimal size selection for the gates in a combinatorial circuit which uses the problem of finding a shortest path in an oriented acyclic graph for making certain updates between any two successive iterations. For this NP-hard problem, we give an approximation algorithm. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53521.html 04:00 PM Wednesday 31, 1969 The topic of this paper is the cyclic job shop problem, short CJSP, which aims at minimizing the cycle time under precedence and resource constraints. Based on graph theory, we propose a new branch and bound enumeration procedure to solve the CJSP. We compare the new procedure with other exact methods and present numerical test results. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53523.html 04:00 PM Wednesday 31, 1969 In this contribution we discuss an extension of a recent approach to solve batch scheduling problems using reachability analysis for timed automata (TA) with embedded lower bound computations. We propose two bounding procedures embedded in the reachability algorithm to handle scheduling problems with sequence-dependent changeovers: (i) a MILP formulation (originally proposed by Manne 1960) extended with additional constraints to model setup and changeover operations and (ii) an improved minimum remaining processing time (MRPT) procedure. The efficiency of the proposed bounding procedures is evaluated on job shop problems with sequence-dependent changeovers. The comparative study shows that the MRPT-based bounding procedure is efficient and increases the overall performance significantly in comparison to the MILP-based bounding procedure. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53525.html 04:00 PM Wednesday 31, 1969 We present an approach on a two-stage filtration of the set of feasible solutions for multiprocessor job-shop scheduling problem. On the first stage, we use extensive dominance relations, whereas on the second stage we use lower bounds. We show that several lower bounds can efficiently be obtained and implemented. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53527.html 04:00 PM Wednesday 31, 1969 A problem of train timetabling for a single-track railway is studied using a disjunctive graph model for the corresponding job-shop. The objective is to minimize the total weighted tardiness of the given trains. A shifting bottleneck algorithm is developed and tested to get a close to optimal schedule to the job-shop problem. At each iteration, this algorithm tries to minimize the total weighted tardiness of jobs (trains) with the given release times (departure times of the trains), the due dates, and the processing times on a single machine (single-track section between two stations). Since the latter problem is unary NP-hard, a heuristic procedure is used at each iteration of the shifting bottleneck algorithm. Computational results demonstrate the dependence of the CPU-time on the number of trains and single-track sections. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53529.html 04:00 PM Wednesday 31, 1969 We propose a polynomial-time algorithm that solves the problem of scheduling jobs with two possible processing times on unrelated machines with the objective to minimize the maximal job completion time. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53531.html 04:00 PM Wednesday 31, 1969 This paper deals with multi stage jobshop scheduling problem. At each stage, either a fix or a variable number of identical parallel machines are available to execute jobs operations. As often in industrial environment, no space is available between machines, a specific RCb blocking constraint is taken into account. A linear integer mathematical model is proposed and executed in X-Press software to solve short size instances of this problem and to validate proposed model. In order to be able to evaluate future heuristics solutions quality, four lower bounds are proposed, computed and evaluated with benchmark for symmetric and asymmetric resources repartition cases. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53533.html 04:00 PM Wednesday 31, 1969 In this paper we discuss scheduling problems with impatience to the beginning and to the end of service. The impatience of a job can be seen as a due date and processing times and due dates are random variables. Jobs are processed on a single machine with the objective to minimize the expected weighted number of tardy jobs in the class of static list scheduling policies. We derive optimal schedules when processing times and due dates are exponentially distributed. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53535.html 04:00 PM Wednesday 31, 1969 We investigate the problem of minimizing the weighted number of tardy jobs on a single machine subject to availability constraints. We consider the case of semi-resumable jobs ($1,h_k|r_i,sr-a|sum w_iU_i$). We show that the problem is equivalent to a similar problem without availability constraints, but where the processing times of jobs are a stepwise function of their starting time. We design a Mixed Integer Linear Program (MILP) to model the problem and solve it with help of a commercial MILP solver. Computational experiments on randomly generated instances show that using this method allows solving optimally most $300$-job problems within $1000$ seconds, and provides excellent heuristic solutions in $100$ seconds. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53537.html 04:00 PM Wednesday 31, 1969 We consider the problem of scheduling jobs with release times and due dates on a single machine to minimize the maximal job lateness. This problem is NP-hard, and its version when the job processing times are restricted to p,2p,3p,4p,..., for an integer p, is also NP-hard. We consider the case when the maximal job processing time is kp, for any constant k, and propose its polynomial-time solution. We easily establish that the version of this problem with unrestricted k is NP-hard. Moreover, it is strongly NP-hard if p has no exponential-time dependence on the maximal job due date. From a practical point of view, this is a realistic assumption. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53539.html 04:00 PM Wednesday 31, 1969 In this paper, we consider the NP-hard minimizing total tardiness on a single machine scheduling problem. We propose a metric for that problem and present a polynomial approximation scheme based on search for the polynomially solvable instance which has a minimal distance from an initial instance. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53541.html 04:00 PM Wednesday 31, 1969 In this paper, we present a modification of dynamic programming algorithms (DPA), which we denote as graphical algorithms (GrA). For some single machine scheduling problems, it is shown that the time complexity of the GrA is less than the time complexity of the standard DPA. Moreover, the average running time of the GrA is often essentially smaller. A GrA can also solve large-scale instances and instances, where the parameters are not integer. For some problems, GrA has a polynomial time complexity in contrast to a pseudo-polynomial complexity of a DPA. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53543.html 04:00 PM Wednesday 31, 1969 Abstract: The use of hybrid dynamical systems theory opens a new horizon for flexible manufacturing systems scheduling. It makes even possible directly connect scheduling and MRP. In the present paper the most important new result is the proposed demand rates determination method for multi-section scheduling problems. Some other important achievements making possible the application of this approach are discussed, too. These are, for example: • feedback control law resulting stable (implementable with finite buffers) and regular ( converging to periodic) processes • optimal demand rates determination for single- section problems Keywords: Flexible manufacturing systems; Scheduling; Hybrid dynamical systems; Single -sections; Multi-sections; Stability; Periodic regimes; Optimal demand rates; Buffers, Bottleneck, Automatic lot-streaming; Overlapping production;; Self-organizing; Distributed; Real-time control; MRP http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif http://www.ifac-papersonline.net/Detailed/53545.html 04:00 PM Wednesday 31, 1969 For an assembly line, it is necessary to minimize the cycle time for processing a partially ordered set of operations V = {1,..., n } on a set of m linearly ordered working stations. The number m of stations and the initial processing times t = (t_1, ..., t_n) of the operations V are given. However, for a subset of the manual operations, it is impossible to fix the processing times for the whole life cycle of the assembly line. On the other hand, for each automated operation, the processing time is fixed. We investigate the stability of an optimal line balance b_0 of the assembly line with respect to variations of the processing times. It is shown how to calculate the stability radius of an optimal line balance b_0, i.e., the maximal value of simultaneous independent variations of the processing times of the manual operations with keeping the optimality of the line balance b_0. We survey known results on the stability radius of an optimal line balance for a dual problem which is to minimize the number m of the working stations for the given cycle time. http://www.ifac-papersonline.net/static/luna/images/ifac/icon-download.gif