外文原文.pdf

Discrete Optimization Modeling the reentrant job shop scheduling problem with setups for metaheuristic searches Jeriad Zoghby *, J. Wesley Barnes, John J. Hasenbein Graduate Program in Operations Research and Industrial Engineering, Department of Mechanical Engineering, The University of Texas at Austin, Austin, TX 78712, USA Received 10 December 2001; accepted 31 March 2004 Available online 8 June 2004 Abstract We consider modeling the reentrant job shop scheduling problem with sequence dependent setup times in the context of metaheuristic search methods. We begin by investigating feasibility conditions when sequence dependent setups are incorporated into the traditional job shop scheduling problem. The investigation reveals that traditional methods of avoiding infeasible solutions for iterative search techniques do not suffi ce. The conditions under which these infeasible solutions occur are presented and an algorithm is presented to remove such infeasibilities. Reentrancy and its rela- tionship to the traditional model are then illustrated, and the new features of the disjunctive graph are introduced. We conclude with a simple algorithm for obtaining an initial feasible solution, benefi ts of this research, and an application to the reentrant job shop scheduling problem with sequence dependent setups. ? 2004 Elsevier B.V. All rights reserved. Keywords: Metaheuristics; Scheduling; Flexible manufacturing systems; Manufacturing; Graph theory 1. The disjunctive graph model In this paper, we consider a variation of the classical job shop scheduling problem, the reentrant job shop scheduling problem with sequence depen- dent setups. This is an extension of the classical job shop scheduling problem, denoted Jmkc, which is introduced and defi ned in Section 2.1. The reen- trant job shop scheduling problem with sequence dependent setups, denoted Jmjsjk;recrcjc, extends the classical model by allowing for sequence dependent setup times between adjacent opera- tions on any machine and relaxing the restriction that each job visits a machine only once. The Jmkc is a well-known NP-hard problem 17, which has spurred an extensive and rapidly growing body of literature. Much of the recent research has revolved around dispatching rules, decomposition methods, and metaheuristic search techniques. Simple heuristic rules have dominated this area of research 27. Least slack policies and bottleneck starvation policies are scheduling techniques based *Corresponding author. Present address: 646 S. Main Ave., San Antonio, TX 78204, USA. Tel.: +1-210-938-7386; fax: +1- 210-938-3138. E-mail addresses: , jmzmail.utexas. edu (J. Zoghby), (J. Wesley Barnes), (J.J. Hasenbein). 0377-2217/$ - see front matter ? 2004 Elsevier B.V. All rights reserved. doi:10.1016/j.ejor.2004.03.027 European Journal of Operational Research 167 (2005) 336348 /locate/dsw on pulling WIP (work in progress). Least slack policies pull WIP to the end of the process line based on due dates or estimated cycle times 29,30. Bottleneck starvation policies pull WIP to the bottleneck based on Goldratts Theory of Constraints 19,20,28. There are also a consider- able number of other dispatching rules that have been developed across many industries 9,33. Decomposition methods attempt to develop solutions to complex problems by decomposing them into a number of smaller subproblems which are more tractable and easier to understand 32. The most successful of these methods, the Shifting Bottleneck approach 1,2,22, takes advantage of the disjunctive graph structure introduced by Roy and Sussman 34. By decomposing the problem into a series of single-machine subproblems, the technique iteratively schedules each machine while focusing on the bottleneck 35. Branch and bound methods have also incorporated a decomposition model 10, but generally perform very poorly on large problems due to the excessive computing time. Like decomposition methods, metaheuristics use the disjunctive graph model of the Jmkc. However, many metaheuristics rely heavily on guidance provided by Balas 3 to maintain feasi- bility during the search. For problems without sequence dependent setups, Balas showed that reversing arcs on the critical path maintains fea- sibility, and that such arc reversals are the only single reversals that could lead to improved solu- tions. Balas insights are the key to developing iterative methods, which can effi ciently search the complex solution space of the Jmkc. The last two decades have seen the growth of metaheuristic techniquessuccessfullyappliedtoproduction schedulingproblems57,12,13,18,25.Genetic algorithms, which do not necessarily use the dis- junctive graph, have been applied to these types of problems 8,11,21,24,31, but without considering the underlying structure or investigating the fea- sibility conditions of these models. Although there is substantial research with regard to Flow Shop Scheduling Problems with setups 15, they do not pose the same feasibility issues as Jmkc problems. The purpose of the paper is to present structural results and algorithms based on the disjunctive graph formulation of the Jmjsjk;recrcjc. Our belief is that investigation of this structure can lead to improved metaheuristic search methods for this problem, however we do not pursue an empirical investigation here. We present a disjunctive graph formulation of the problem and results related to the nature of feasible solutions represented in the graph. We also provide an ejection chain algo- rithm to return infeasible solutions to feasibility. We begin by extending the Jmkc to allow sequence dependent setups (Jmjsjkjc). We then further ex- tend this model to allow for reentrancy, where jobs are allowed to revisit machines (Jmjsjk;recrcjc). The purpose of presenting these extended models is to allow for metaheuristic techniques, such as Tabu Search, to perform effi cient searches of the feasible solution space. In Section 2, we begin with a brief recounting of the disjunctive graph formulation of the Jmkc 34 and the rule that guarantees feasibility while per- forming iterative moves toward the solution of the Jmkc 3. We then present a simple counterexample to the feasibility rule in a Jmjsjkjc disjunctive graph. The example illustrates that reversing a disjunctive arc on the critical (longest) path may not guarantee feasibility, i.e., a subsequent acyclic disjunctive graph, when one or more machine sequence dependent setups are present. These set- up-induced infeasibilities are then examined to determine the conditions under which they occur and an algorithm is presented which will remove any cycles that are formed. The Jmjsjkjc is then further extended to form the Jmjsjk;recrcjc, which allows for machines to be revisited, i.e., a job may possess two or more operations that require the same machine. The Jmjsjk;recrcjc and its rela- tionship to the Jmjsjkjc are then detailed. We conclude with an algorithm for fi nding an initial feasible solution for the Jmjsjk ;recrcjc, benefi ts of the research, and an industrial application. 2. The disjunctive graph model Much of the metaheuristic research on the Jmkc has relied upon the work of Roy and Sussman 34 and Balas 3. By modeling the problem as a dis- junctivegraph,RoyandSussmanpermitted J. Zoghby et al. / European Journal of Operational Research 167 (2005) 336348337 researcherstocaptureimportantscheduling information in a simple model. Balas extended their work by iteratively fi nding better solutions while maintaining feasibility from iteration to iteration. Balas work is the key to the success of many metaheuristic approaches, providing guid- ance on maintaining feasibility and avoiding non- improving moves. 2.1. The job shop scheduling problem The JmkCmaxconsists of a set # of n jobs, a set M of m machines, and a set O of N operations. Each operation v 2 O belongs to a job Jv2 # and is processed on a machine Mv2 M for a processing time of pv2 R . There is also a binary relation fi from O to O that defi nes the technological prece- dence of operations v;w belonging to the same job, Jv Jw. The problem of minimizing the makespan reduces to fi nding a release time rvfor each oper- ation v 2 O such that MiniMax v2O rv pv1 subject to rw? rvPpvif v ! w; v;w 2 O;2 rw? rvPpv_ rv? rwPpw if Mv Mw; v;w 2 O;3 rvP08v 2 O:4 In order to solve this problem via metaheuristic techniques it is advantageous to represent it as a disjunctive graph model. The disjunctive graph G V ;A;E consists of a set of nodes V , con- junctive arcs A, and disjunctive arcs E defi ned as follows: V O f0;N 1g, where 0 represents a source node, N 1 represents a sink node, both of which are virtual nodes not representing actual operations. A fv;wjv;w 2 O;v ! wg f0;wjw 2 O; 9 =v 2 O : v ! wg fv;N 1jv 2 O; 9 =w 2 O : v ! wg, where these arcs defi ne the technolog- ical precedence of operations within each job, and the relationships between jobs and the source and sink nodes. This set defi nes the con- junctive arcs, which have fi xed orientation and defi ne the technological precedence in the graph. The arc length defi nes the amount of time re- quired to process the operation at the tail of the arc. For arcs (0, w), the arc length can be used to represent the release delay for job Jw. E fv;wjMv Mw g, where these arcs defi ne the order of processing for operations on the same machine. These arcs represent the con- straint (3) above, and the orientations of these arcs defi ne the current solution of the graph. Fig. 1 presents an example of a disjunctive graph of a Jmkc with 3 machines, 3 jobs, and 3 operations per job. Node sets f1;2;3g, f4;5;6g, and f7;8;9g defi ne the operations for the 3 jobs, and node sets f1;5;9g, f2;4;8g, and f3;6;7g partition the operations among the 3 machines. The conjunctive arcs are denoted by solid lines and have a fi xed orientation, while disjunctive arcs are denoted by dashed lines and have no a priori fi xed orientation. Conjunctive arc lengths represent the time required before the job can begin a new operation. Disjunctive arc lengths represent the time required before the machine is free to begin processing the next operation. A selection of dis- junctive arc orientations represents a distinct ordering of operations on each machine. A new feasible solution can be found by reversing the orientation of a disjunctive arc on the critical (longest) path in the graph 3. Feasibility can be maintained by limiting the candidate arcs for reversal to disjunctive arcs on the critical path in the graph, given that the current solution is feasible. Balas proved that only arc reversals on the critical path could make iterative improvements in the makespan of the JmkCmax3. Fig. 1. The disjunctive graph of the Jmkc. 338J. Zoghby et al. / European Journal of Operational Research 167 (2005) 336348 By switching critical path disjunctive arcs, meta- heuristic search algorithms are able to effi ciently search the feasible solution space for improving solutions. 2.2. The job shop scheduling problem with setups Sequence independent setup delays are easily incorporated into the classical model and require no change in the iterative procedure. Such a delay is simply added to the duration of all arcs origi- nating at an operation node 3. A sequence dependent setup imposes an extra delay, in addi- tion to the current operation processing time, be- fore a particular machine can begin working on the next operation in its sequence. In the Jmjsjkjc, this sequence dependent setup time is added only to the unique associated disjunctive arc. Reversing an arc on the critical path does not always guarantee feasibility. The simple Jmjsjkjc model of Fig. 2 with 2 jobs, 4 operations, and 2 machines illustrates this fact. In Fig. 2, a single sequence dependent setup time of 12 units is present and takes place only when operation 3 precedes operation 2. Therefore, Arc 3;2 has a length of 17 while Arc 3;4 has a length of 5. This implies that the processing time for operation 3 is 5 time units, while the sequence dependent setup delay of operation 3 preceding operation 2 is 12 time units. The critical path of the graph is f0;3;3;2;2;5g, which has a length of 22. Arc 3;2 is the only disjunctive arc on the critical path in the current graph. However, its reversal creates the cycle f3;4;4;1;1;2;2;3g. Therefore the current graph cannot move to another feasible solution by only considering arcs on the longest path. An arc is a Cycle Generating Arc (CGA), when it is on the critical path and its reversal will create a cycle. An algorithm to remove cycles from the disjunctive graph is presented later. Sequence dependent setups are added only to the disjunctive arcs. If they are added to both the disjunctive and conjunctive arcs in the graph, this is equivalent to setups not beginning until both the job and machine are available. However, in a deterministic scheduling environment, the next operation is assumed to be known and delaying a setup until a job arrives would be ineffi cient if a machine is idle anyway. Although such setups could lead to an ineffi cient schedule, they would also avoid creating cycles in the graph, since the conjunctive and disjunctive arcs originating at a node would be of equal length. Our example shows that feasibility of the Jmjsjkjc is not guaranteed when reversing arcs on the critical path. This illustrates a concern when applying metaheuristic techniques to solve this problem. Critical path arcs are still the only arcs whose single reversal can improve the solution of the makespan 3. However, feasibility can no longer be guaranteed when searching the solution space by such reversals. The next section investi- gates the cycles created by single arc reversals and provides the necessary criteria for their existence. 3. Investigating cycles in the disjunctive graph A cycle composed only of disjunctive arcs im- plies the illogical condition in the schedule that an operation performed by a particular machine must precede itself. Our results below implicitly assume that these cycles can be avoided when moving between the solutions in a job shop problem. Cy- cles which are composed only of disjunctive arcs are referred to as DA (disjunctive arc) cycles. Any cycle not in the class of DA cycles is called a NDA cycle (non-disjunctive arc cycle). It can be shown that some classes of job shop problems cannot contain DA cycles. For example, White and Rogers37showthatifacertaintriangle inequality involving the sequence dependent setup times is satisfi ed for all triplets of operations, than a DA cycle is not possible in the disjunctive graph representation of the problem. Even if DA cyclesFig. 2. Infeasible example of the Jmjsjkjc. J. Zoghby et al. / European Journal of Operational Research 167 (2005) 336348339 are possible, they can be explicitly avoided in a software representation of the problem by model- ing machine cliques via arrays 1. Therefore, un- less stated otherwise, graphs considered in the rest of this paper are assumed not to contain DA cycles. To fully understand when solution infeasibili- ties occur, some basic propositions must be con- structed. All propositions in this section apply to the Jmkc, Jmjsjkjc, and Jmjsjk;recrcjc. Proposition 1. For any cycle to be created by reversing disjunctive Arc i;j, an alternate path must exist from nodes i to j. Proof. This was proven by Balas 3 for the Jmkc problem. The proofs for Jmjsjkjc and Jmjsjk;recrcjc are exactly analogous.h Proposition 2. Consider a solution which is feasible (i.e. does not contain any cycles) and a disjunctive arc v;w which is on the critical path. Suppose that reversal of arc v;w creates a NDA cycle and does not create any DA cycles. Then this NDA cycle contains a conjunctive arc originating from node v and a conjunctive arc terminating at node w. Proof. Consider a feasible solution in the disjunc- tive graph. Suppose disjunctive critical path arc (v;w) is such that its reversal to arc w;v creates an NDA cycle. In particular, there exists an alternate path from v to w. We show that the NDA cycle created must contain a conjunctive arc orig- inating from node v. We prove this by contradiction. So, suppose instead that all arcs originating from node v which are on the alternate path are disjunctive. Now consider a particular disjunctive arc on the alter- nate path v;u, where u is diff erent from w. Since disjunctive arcs v;w and v;u exist, this implies that operations (nodes) v;w;u are all assigned to the same machine. Therefore, there must exist a disjunctive arc connecting w and u. Furthermore, since node u is part of the alternate path from v to w, there is a path from u to w. Since the previous solution was feasible (before reversal of arc v;w), the disjunctive arc connecting nodes w and u must originate at nodeu as shown in Case II of Fig. 3. If not, then the previous solution was not feasible (as shown in Case I of Fig. 3). However, this implies that a DA cycle is created when arc v;w is re- versed. This contradicts our assumption that the reversal of v;w does not create any DA cycles. Hence, not all arcs on the alternate path which originate at node v can be disjunctive, i.e. there exists a conjunctive arc originating from node v in the cycle created by reversing arc v;w. Using a directly analogous argument, it can be shown that under the assumptions of the theorem a conjunctive arc terminates at node w.h Proposition 2 implies that a NDA cycle must contain at least two conjunctive arcs and one dis- junctive arc (the arc being reversed). Proposition 3 shows that a NDA cycle must contain at least one other disjunctive arc. Proposition 3. All NDA cycles require at least 4 arcs. At least 2 of these arcs ar