A survey of scheduling problems with setup times or costs <s> Conclusions <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> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Conclusions <s> Lot splitting is a technique for accelerating the flow of work by splitting job lots into sublots, In this paper we investigate the lot splitting scheduling problem in a two-machine flow-shop environment with detached setups and with batch availability. The performance measure considered is the average flow-time which is indicative of the increasingly important manufacturing lead-time. Our contribution is both theoretic and practical for the case of general (not necessarily equal) sublots. We identify properties of the optimal solution and develop a solution procedure to solve the problem. We then present a computational study which indicates that our solution technique is very efficient. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Conclusions <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> BIB003 </s> A survey of scheduling problems with setup times or costs <s> Conclusions <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> BIB004 </s> A survey of scheduling problems with setup times or costs <s> Conclusions <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> BIB005 </s> A survey of scheduling problems with setup times or costs <s> Conclusions <s> AbstractThis paper considers a scheduling problem in which a single operator completes a set of n jobs requiring operations on two machines. The operator can perform only one operation at a time, so when one machine is in use the other is idle. After developing general properties of optimal schedules, the paper develops efficient algorithms for minimizing maximum lateness. The algorithm has time complexity O(n) (after due date sorting) for both the open shop and How shop cases. <s> BIB006 </s> A survey of scheduling problems with setup times or costs <s> Conclusions <s> The two-stage assembly scheduling problem is a model for production processes that involve the assembly of final or intermediate products from basic components. In our model, there are m machines at the first stage that work in parallel, and each produces a component of a job. When all components of a job are ready, an assembly machine at the second stage completes the job by assembling the components. We study problems with the objective of minimizing the makespan, under two different types of batching that occur in some manufacturing environments. For one type, the time to process a batch on a machine is equal to the maximum of the processing times of its operations. For the other type, the batch processing time is defined as the sum of the processing times of its operations, and a setup time is required on a machine before each batch. For both models, we assume a batch availability policy, i.e., the completion times of the operations in a batch are defined to be equal to the batch completion time. We provide a fairly comprehensive complexity classification of the problems under the first type of batching, and we present a heuristic and its worst-case analysis under the second type of batching. <s> BIB007 </s> A survey of scheduling problems with setup times or costs <s> Conclusions <s> In many practical situations of production scheduling, it is either necessary or recommended to group a large number of jobs into a relatively small number of batches. A decision needs to be made regarding both the batching (i.e., determining the number and the size of the batches) and the sequencing (of batches and of jobs within batches). A setup cost is incurred whenever a batch begins processing on a given machine. This paper focuses on batch scheduling of identical processing-time jobs, and machine- and sequence-independent setup times on an m-machine flow-shop. The objective is to find an allocation to batches and their schedule in order to minimize flow-time. We introduce a surprising and nonintuitive solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004 <s> BIB008 </s> A survey of scheduling problems with setup times or costs <s> Conclusions <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> BIB009 </s> A survey of scheduling problems with setup times or costs <s> Conclusions <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> BIB010 </s> A survey of scheduling problems with setup times or costs <s> Conclusions <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> BIB011
We have surveyed more than 300 papers on scheduling with setup times (costs) that have appeared since 1999. On average, more than 40 papers per year have been added to the related literature. As compared to the 190 papers surveyed by Allahverdi et al. (1999) in over 25 years (i.e., about 8 papers per year), there has been a huge jump in the annual research output on scheduling with setup times (costs) in the past six years. This survey classifies the literature on setup times (costs) according to (1) shop environments, including single machine, parallel machines, flow shops, job shops, open shops, and others; (2) batch and non-batch setup times (costs); (3) sequence-dependent and sequence-independent setup times (costs); and (4) job and batch availability models. The research status on different problem types is reviewed and summarized in Tables 1-8 . Single machine, parallel-machine, flow shop, job shop and open shop problems were addressed in about 80, 70, 100, 20 and 10 papers, respectively. For single machine problems, three quarters of the papers considered batch setup times while only one quarter of the papers discussed non-batch setup times. For other shop environments, this trend was not the case. For example, for the parallel machine case, the majority of the papers considered non-batch setup times. Moreover, two thirds of the papers on flow shop problems addressed the non-batch setup times. The majority of the papers addressed sequence-independent setup times because dealing with sequence-dependent setup times is more difficult. The common solution methods are branchand-bound algorithms, mathematical programming formulations, dynamic programming algorithms, BIB001 2 C max Strongly NP-hard, 4/3-approximation algorithm Lin and Cheng (2001) 2 (no-wait) C max Strongly NP-hard, polynomial algorithms for special cases BIB002 2 P C j (non-integer batch sizes) Convex programming, optimal solution for a special case BIB007 m + 1 (assembly) C max A heuristic with tight worst case performance bound of 2 À 1/ (m + 1) BIB008 m C max , P C j , p j = p O(n), rounding optimal noninteger batch sizes heuristics and meta-heuristics. Among metaheuristic methods, genetic algorithms were used in about 35 papers while tabu search was used in about half of this number of papers. Simulated annealing was BIB003 C max Mixed integer programming BIB004 C max Mixed integer programming, a local search algorithm  C max Tabu search  C max (reentrant job shop) Heuristics, genetic algorithm BIB009 C max Branch-and-bound algorithm Artigues et al. (in press) C max Upper bounds, priority rule-based multi-pass heuristic  C max Integration of tabu search and multi-pass heuristics BIB011 C max (r j ) Shifting bottleneck procedure, dynamic programming  P T j (r j , precedence constraints, hybrid job shop) Ant colony BIB010 General ( C max Disjunctive graph presentation, integer programming algorithm Table 8 Open shop scheduling problems Strusevich (2000) C max (2-machine) Worst-case performance ratio, linear-time heuristic BIB001 C max (2-machine) NP-hard in the ordinary sense, heuristic BIB005 P C j (2-machine, group technology) NP-hard, problems with and without group technology assumption are not equivalent BIB006 L max (2-machine, continuous presence of an operator) O(n log n) Mosheiov and Oron (in press-b) C max , P C j (p j = p, batch availability) Constant time for C max , O(n) heuristic for P C i also used in several papers but less than tabu search. Few papers utilized ant colony while particle swarm optimization (PSO) was only used in one paper. The performance of these heuristics, to some extent, depends on different parameters and the operators used as well as on the characteristics and size of problem instances. In some cases, the use of local search methods, while in some other cases, that of hybrid meta-heuristics shows better results. This indicates that different methods have their strengths and weaknesses. In Table 9 , we present the problems for which the computational complexity was reported as unknown in the latest literature. Problems open with respect to strong NP-hardness are marked with an asterisk. We assume a reasonable encoding scheme (see  for each problem, i.e., if the problem formulation explicitly states that there are k parameters equal to a, all these parameters are encoded with two numbers k and a. The most vexing open problem is 1=ST si;b = P C i . Some classes of problems and solution methods have received less attention of the research commu- nity than the others. In Table 10 , we enumerate some of these classes and give plausible reasons for their being less studied. New trends in scheduling with setup times or costs include investigation of problems with resource-dependent job and setup parameters, job and setup deterioration, and job or batch transportation. Corresponding applications of such models are found in supply chain management and logistics. For flow shop, job shop, and open shop problems, the vast majority of the surveyed papers addressed completion time based performance measures (C max ; P j ). Therefore, future research on these problems should be more focused on due date related performance measures (L max ; T max ; P T j ; P U j ). Only few papers addressed multi-criteria scheduling problems with setup times. Since most practical problems involve both setup times and multiple objectives, future research on scheduling problems with setup times to optimize multiple objectives is both desirable and interesting. Stochastic scheduling problems, where some characteristics of the job are modeled as random variables and/or machines may be subject to random breakdowns, with separate setup times, have been addressed only in a few papers. Therefore, another worthy direction of research is to address stochastic scheduling problems with separate setup times. The number of case studies has considerably increased over the last several years. Most of them are limited to planning activities in manufacturing. However, we believe that setup/cost scheduling models have great potential to be applied in such areas as logistics, telecommunications, electronic auctions and trade, and high-speed parallel computations. Our final conclusion is that if the number of publications on scheduling with setup times or costs continues to grow at the present pace, which we expect to be the case as scheduling research in this area is a fertile field for future research, we suggest that future surveys in this area be devoted to either particular classes of these problems, e.g., based on shop environment, or be focused on specific solution methods. 