A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> In this paper a general shop scheduling problem with sequence dependent setup times and alternative resources is considered, where optimization criteria are both makespan and sum of setup times. Two cooperative models for the problem based on Constraint Programming are proposed. The first is used to model the scheduling constraints, while the second is a multi-path model used for setup optimization. Integrating lower bounding techniques for the sum of setup times, the multi-path model performs propagation based on reduced cost fixing. A solution method based on a two phase algorithm is described, and a computational study is performed both on instances known from literature as on newly proposed instances. It is shown that the cooperation of the two models significantly improves performance. Although the aim of the paper is to study the problem including alternative resources, for several known instances without alternative resources, we were able to improve on the best known results. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule isNP-hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP-hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore{Gomory traveling salesman problem and solve it in polynomial time. c 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304{328, 2000 <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> This paper studies the problem of scheduling jobs in a two-machine open shop to minimize the makespan. Jobs are grouped into batches and are processed without preemption. A batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. For this NP-hard problem, we propose a linear-time heuristic algorithm that creates a group technology schedule, in which no batch is split into sub-batches. We demonstrate that our heuristic is a 54-approximation algorithm. Moreover, we show that no group technology algorithm can guarantee a worst-case performance ratio less than 54. <s> BIB003 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> The importance of job shop scheduling as a practical problem has attracted the attention of many researchers. However, most research has focused on special cases such as single machine, parallel machine, and flowshop environments due to the “hardness” of general job shop problems. In this paper, a hybrid algorithm based on an integration of a genetic algorithm and heuristic rules is proposed for a general job shop scheduling problem with sequence-dependent setups (Jm|sjk|Cmax ). An embedded simulator is employed to implement the heuristic rules, which greatly enhances the flexibility of the algorithm. Knowledge relevant to the problem is inherent in the heuristic rules making the genetic algorithm more efficient, while the optimization procedure provided by the genetic algorithm makes the heuristic rules more effective. Extensive numerical experiments have been conducted and the results have shown that the hybrid approach is superior when compared to recently published existing methods for the same problem. <s> BIB004 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> Two efficient cyclic scheduling heuristics for re-entrant job shop environments were developed. Each heuristic generated an efficient and feasible cyclic production schedule for a job shop in which a single product was produced repetitively on a set of machines was to determine an efficient and feasible cyclic schedule which simultaneously minimized flow time and cycle time. The first heuristic considered a repetitive production re-entrant job shop with a predetermined sequence of operations on a single product with known processing times, set-up and material handling times. The second heuristic was a specialization of the first heuristic where the set-up for an operation could commence even while the preceding operation was in progress. These heuristics have been extensively tested and computational results are provided. Also, extensive analysis of worst-case and trade-offs between cycle time and flow time are provided. The results indicate that the proposed heuristics are robust and yield efficient and ... <s> BIB005 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> Abstract This paper presents a Petri net model in the framework of a general method for on-line scheduling in a job shop environment with multi-resource requirements and setup times. The Petri net is based on a precise characterization of significant states, decisions and events for on- and off-line scheduling. A set of solutions to a static scheduling problem represented by an acyclic directed graph is assumed to be predetermined, as input of the proposed decision support system for shop floor scheduling. This system takes account of occurring events to suggest the appropriate scheduling decisions in real time and update the set of solutions accordingly. <s> BIB006 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these asconsistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested. <s> BIB007 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> In this paper we consider the classical representation of job-shop scheduling problems in terms of disjunctive graphs. We derive a mixed integer-linear programming model that keeps track of the immediate precedence relation between operations. Finally, we show how this framework can be used to solve job-shop scheduling problems with sequence-dependent set-up times. Two cases are considered: the set-up operation required before processing a job on a machine may start as soon as the machine is available, or only if both job and machine are available. <s> BIB008 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> Alternative operation sequences and sequence-dependent setups are two important factors that frequently appear in various manufacturing environments and in project scheduling. This paper addresses a jobshop scheduling problem with these factors simultaneously considered. In it, a mixed integer program model of the problem is presented, along with a local search scheme. The local search scheme utilizes a property identified to reduce computation time. In addition, a property that establishes a performance bound is presented. Results from a comparative computational study using benchmark data show that the scheme significantly enhances the performance of several greedy-based dispatching rules for the problem under consideration. <s> BIB009 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> The problems of scheduling groups of jobs under the group technology assumption are studied. The two remaining open questions posed in the literature a decade ago about the computational complexity of these problems (J. Oper. Res. Soc., 1992; 43:395–406), are answered. The parallel machine problem to minimize the total job completion time is proved to be NP-hard in the strong sense, even if group set-up times are equal to zero. A dynamic programming algorithm is presented to solve this problem, which is polynomial if the number of machines is fixed. The two-machine open-shop problem to minimize the makespan is proved to be NP-hard in the ordinary sense, even if there are zero group set-up times and equal job processing times on both machines. It is shown that the latter problem under the condition that any group can be split into batches does not reduce to the problem where the splittings are not allowed, i.e. the group technology assumption is satisfied. Copyright © 2002 John Wiley & Sons, Ltd. <s> BIB010 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> We propose a new solution approach for the Job Shop Problem with Sequence Dependent Setup Times (SDST-JSP). The problem consists in scheduling jobs, each job being a set of elementary operations to be processed on different machines. The objective pursued is to minimize the completion time of the set of operations. We investigate a relaxation of the problem related to the traveling salesman problem with time windows (TSPTW). Our approach is based on a Branch and Bound procedure, including constraint propagation and using this relaxation. It compares favorably over the best available approaches from the literature on a set of benchmark instances. <s> BIB011 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> As the lot-streaming concept has been used widely to reduce the makespan in a production system, most research has investigated the flow shop production systems; however, job-shop production systems have received much less attention, relatively. This study more thoroughly investigates the application of lot splitting in a job shop production system with setup times, which cannot be omitted. The objective investigated not only minimises the makespan but also minimises the total production cost, which includes the material handling cost, the setup cost and the inventory cost. A disjunctive graph is first used to describe the addressed scheduling problem, and an integer programming model is then constructed to obtain an optimal solution. In order to investigate the influence of the number of sublots and sublot sizes on a job-shop production system with regard to the corresponding objective considered, some experiments are conducted and results presented as well. <s> BIB012 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> 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 suffice. The conditions under which these infeasible solutions occur are presented and an algorithm is presented to remove such infeasibilities. Reentrancy and its relationship 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, benefits of this research, and an application to the reentrant job shop scheduling problem with sequence dependent setups. <s> BIB013 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> Abstract In the routing open-shop problem, jobs are located at nodes of a transportation network, and the machines travel on the network to execute jobs. For the makespan-minimizing two-machine routing open-shop problem on a two-node network (which is NP-hard) we prove that the optimum objective value of any instance lies within the interval [ C ∼ , 6 5 C ∼ ] and this interval is tight. C ∼ is a trivial lower bound on the optimum objective value. Based on this result, we obtain a linear time approximation algorithm for this problem with approximation ratio not greater than 6 5 . From the tightness of the interval above it follows that this algorithm gives the best possible approximation in terms of C ∼ . The problem is equivalent to a variant of the two-machine open-shop problem with batch setup times with two batches. <s> BIB014 </s> A survey of scheduling problems with setup times or costs <s> Job shop and open shop <s> In the last 15 years several procedures have been developed that can find solutions of acceptable quality in reasonable computing time to Job Shop Scheduling problems in environments that do not involve sequence-dependent setup times of the machines. The presence of the latter, however, changes the picture dramatically. In this paper we adapt one of the best known heuristics, the Shifting Bottleneck Procedure, to the case when sequence dependent setup times play an important role. This is done by treating the single machine scheduling problems that arise in the process as Traveling Salesman Problems with time windows, and solving the latter by an efficient dynamic programming algorithm. The model treated here also incorporates precedence constraints, release times and deadlines. Computational experience on a vast array of instances, mainly from the semiconductor industry, shows our procedure to advance substantially the state of the art. <s> BIB015
A job shop environment consists of m different machines and each job has a given machine route in which some machines can be missing and some can repeat. On the other hand, in an open shop, each job should be processed once on each of the m machines passing them in any order. BIB004 proposed a hybrid genetic algorithm, based on a genetic algorithm and heuristic rules, for the problem of J/ST sd /C max . They showed by computational analysis that their hybrid algorithm is superior to earlier methods proposed for the same problem. BIB008 considered the same problem and represented it in terms of disjunctive graphs. They also derived a mixed integer linear programming model. BIB009 presented another mixed integer programming model for the same problem and a local search scheme. The local search scheme utilizes a property that reduces computational time. By using benchmark data, BIB009 showed that the scheme significantly enhances the performance of several greedy-based dispatching rules. A fast tabu search heuristic was proposed by  for the problem. Artigues et al. (in press) obtained upper bounds by a priority rule-based multi-pass heuristic. A branch-and-bound procedure was proposed by BIB011 who improved the results obtained by the branch-and-bound procedure presented by BIB001 .  presented a synthesis of the methods described by  , BIB011 , and Artigues et al. (in press ) by integrating tabu search with multi-pass sampling heuristics. The heuristics proposed by BIB004 and  remain to be compared.  addressed the J/ST sd /C max problem but with the additional characteristic of reentrant work flows. They utilized disjunctive graph representation of the problem, and proposed several heuristics including a genetic algorithm. BIB015 formulated the J/ST sd ,r j /C max problem as an asymmetric traveling salesman problem with a special type of precedence constraints, which can be solved by a dynamic programming algorithm whose complexity is linear in the number of operations. The J/ST sd /L max problem was addressed by Artigues and Roubellat (2002), where they proposed a polynomial insertion algorithm to solve the problem. decomposed the J=ST sd ; r j = P w j T 2 j problem into a series of single machine scheduling problems within a shifting bottleneck framework. They solved the problem using a Lagrangian relaxation based approach. The J=ST sd ; r j ; prec= P T j problem was considered by  for the case of hybrid job shop (with identical parallel machines in some stages), where precedence constraints exist between some jobs. They proposed an Ant Colony algorithm and showed by computational analysis that it performs better than a genetic algorithm.  considered the J/ST si,b problem with respect to both regular and non-regular criteria. They proposed different insertion techniques combined with beam search to solve the problem. The insertion techniques were tested on a large collection of test problems and compared with other constructive algorithms based on priority rules. BIB013 investigated the feasibility conditions for metaheuristic searches for the case of reentrancy in the disjunctive graph model of the job shop scheduling problem where the setup times are considered as sequence dependent. They presented the conditions under which infeasible solutions occur and proposed an algorithm to remove such infeasibilities. A job shop problem with families of identical jobs and sequence (of families) independent, machine dependent anticipatory setups to minimize C max was studied by BIB012 . They gave a disjunctive graph presentation of the problem and suggested an integer programming algorithm. A problem in the reentrant job shop environment was considered by BIB005 , where a batch of identical jobs has to be repeatedly processed in a job shop according to a given machine sequence. A machine dependent setup time precedes each batch processing on each machine. The objective is to find a batch size and a (cyclic) schedule such that the flowtime of the batch and the length of one cycle are simultaneously minimized. Two constructive heuristics were proposed. A Petri net approach was suggested by BIB006 for on-line and off-line scheduling of a job shop with job release dates, sequence dependent family setup times and the maximum lateness objective. A set of solutions to a static scheduling problem represented by an acyclic directed graph was assumed to be predetermined, as input of their proposed decision support system for the considered scheduling problem. BIB002 showed that the O2, S/ST si / C max problem is NP-hard in the strong sense when the setup operations are performed by a single server. BIB007 showed that the O2/ST si,b / C max problem is NP-hard in the ordinary sense. BIB003 studied the same problem and proposed a linear time heuristic algorithm. He showed that the algorithm can guarantee a worstcase performance ratio less than 5/4. BIB014 studied a problem that is equivalent to O2/ST sd,b /C max with two families. They proved that the optimal makespan value falls in the interval [C, (6/5)C], where C is a trivially calculated lower bound and suggested an O(n) time algorithm to construct a schedule with makespan from this interval. BIB010 proved the ordinary NP-hardness of the problem O2=ST si;b = P C j under the group technology assumption, and showed that omitting this assumption does not lead to an equivalent problem. A single family open shop problem with equal job processing times and a common non-anticipatory setup time to minimize C max or P C j under the batch availability model was studied by Mosheiov and Oron (in press-b) . They suggested a constant time solution for C max minimization, and an O(n) time heuristic for P C i minimization.