A survey of scheduling problems with setup times or costs <s> Flow shop <s> A flexible manufacturing cell consisting of two machining centres, several automated storage/retrieval stations, and a mobile transporting robot is considered. The problem is to schedule jobs on machines so as to minimize the makespan, with the effects of transportation and set-ups to be taken into account. The problem is studied with the aid of a graph model, and an exact algorithm of cubic complexity is derived based on the Gilmore–Gomory algorithm for the travelling salesman problem. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> This paper presents an enhanced heuristic for minimizing the makespan of the flow shop scheduling problem with sequence-dependent setup times. The procedure transforms an instance of the problem into an instance of the traveling salesman problem by introducing a cost function that penalizes for both large setup times and bad fitness of schedule. This hybrid cost function is an improvement over earlier approaches that penalized for setup times only, ignoring the flow shop aspect of the problem. To establish good parameter values, each component of the heuristic was evaluated computationally over a wide range of problem instances. In the testing stage, an experimental comparison with a greedy randomized adaptive search procedure revealed the conditions and data attributes where the proposed procedure works best. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> This paper addresses a shop scheduling problem for the side frame press shop in a truck manufacturing company. In the problem, a set of n jobs to be scheduled on two machines. All the jobs require processing by the first machine more than once in their operation sequences with reentrant work flows. An unusual aspect of the problem is that the setup times required for a job in the first machine depend not on the immediately preceding job but on the job which is two steps prior to it. Redefining the job elements, the problem is formulated into a general two machine flow shop problem which has a set of job-element precedence constraints. The problem is solved with a modified dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance condition and a decision-delay scheme. A numerical example is presented for the illustration purpose. <s> BIB003 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> The problem of scheduling in a static flowshop with sequence-dependent setup times of jobs (FSDS) is considered in this paper. A new heuristic to minimize the sum of weighted flowtime of jobs in a FSDS is proposed. An improvement scheme is supplemented to enhance the quality of the heuristic solution. An extensive computational performance analysis has shown that the proposed heuristic is computationally faster and more effective in yielding solutions of better quality than the existing heuristic. An interesting observation is that even though the proposed heuristic aims to minimize the sum of weighted flowtime of jobs (just like the existing heuristic), it fares much better than the existing heuristic in minimizing the maximum weighted flowtime of a job too. <s> BIB004 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> This paper addresses a shop scheduling problem where a set of n jobs needs to be scheduled on two machines for the side frame press shop in a truck manufacturing company. A most unusual aspect of the problem is that the setup times required for a job in the first machine depend not on the immediately preceding job but on the job which is two steps prior to it. Redefining the job elements, the problem is formulated into a general two machine flow shop problem which can be solved by dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance conditions and the decisiondelay scheme. Since the computational requirements of dynamic programming are impracticably demanding for large-sized problems, a genetic algorithm is developed and its performance is examined through a comparative study. <s> BIB005 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> A dynamic programming formulation is presented for determining an optimal solution to a problem where n jobs are to be sequenced in a multi-stage production environment. An application of a developed formulation to a plastic pipe manufacturing factory is also presented. Conditions are such that the job sequence is the same in all stages, each job requires setups at each stage and setup times are sequence dependent. An optimal solution is such that the minimum total tardiness is achieved. A listing of the developed computer program is also provided. <s> BIB006 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> Abstract In this paper we study the problem of scheduling n jobs in a one-operator–two-machine flowshop. In such a flowshop, before a machine begins processing a job, the operator has to set up the machine, and then the machine can process the job on its own. After a machine finishes processing a job, the operator needs to perform a dismounting operation before setting up the machine for another job. The setup and dismounting operations are either separable or nonseparable. The objective is to minimize the makespan. Confining our study to cyclic-movement schedules which require the operator to move between the two machines according to some cyclic pattern, we show that both the cyclic-movement separable and nonseparable setup and dismounting problems are NP-complete in the strong sense. We then propose some heuristics and analyze their worst-case error bounds. Scope and purpose The one-worker–multiple-machine (OWMM) concept is widely applied in just-in-time (JIT) manufacturing systems. In an OWMM system, a worker tends several machines simultaneously where each of the machines performs a different operation, and the different machines make up a flow line. In this paper, we study a scheduling problem in the one-operator–two-machine system where the operator moves between two machines according to some cyclic pattern, and performs the setup and dismounting operations on both machines. Both separable and nonseparable setup and dismounting problems are considered. <s> BIB007 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> In this paper we explore flowshop scheduling problems containing both sequence-dependent setup times and finite buffers. To the best of our knowledge, problems containing both of these complexities have not been addressed previously in the literature. The problem is clearly NP-hard and therefore we only consider heuristic solution methods. We propose a tabu search based solution procedure. Computational results demonstrate the effectiveness of this approach relative to the other methods discussed. <s> BIB008 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> This paper addresses the two-machine flowshop problem to minimize mean flowtime where setup times are separated and sequence independent. Optimal solutions are obtained for two special cases. For the general case, two dominance relations are established and their effectiveness in a branch-and-bound algorithm is evaluated. It is shown that problems up to 35 jobs can be solved optimally in a reasonable time. Moreover, for the general case, three heuristic algorithms are proposed to find an approximate solution for larger problems, and they are empirically evaluated to assess their effectiveness in finding the optimal solution. Computational results show that one of the heuristic algorithms has an overall average error of 0.7% from the optimal value and that the error is independent of the number of jobs. ::: ::: ::: Scope and purpose ::: ::: A flowshop scheduling problem involves scheduling a number of jobs on a number of machines in order to optimize a given criterion. The majority of research assumes that setup times are negligible or can be combined with the processing times. However, the latter assumption is invalid in the case of sequence-dependent setup times and may lead to more idle time on some of the machines in the case of sequence-independent setup times. This illustrates the importance of considering setup times as separate from processing times. In the literature, the separate setup times problem has been mainly addressed with the criterion of makespan. Minimizing makespan is important in situations where a simultaneously received batch of jobs is required to be completed as soon as possible. For example, a multi-item order submitted by a single customer that needs to be delivered at the minimal possible time. However, there are other real life situations in which each completed job is needed as soon as it is processed. In such situations, one is interested in minimizing the mean or sum of flow (completion) times of all jobs rather than minimizing makespan. This objective is particularly important in real life situations in which reducing inventory or holding cost is of primary concern. This paper addresses a two-machine flowshop scheduling problem with separate setup times in order to minimize mean flowtime. <s> BIB009 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N 2 + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N 3) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal... <s> BIB010 </s> A survey of scheduling problems with setup times or costs <s> Flow 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> BIB011 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> We consider the problem of scheduling a reentrant flow shop with sequence-dependent setup times to minimize maximum lateness. We develop a series of decomposition methods (DMs) exploring the importance of components such as subproblem solution method, bottleneck identification and reoptimization method on the solution time/quality tradeoff. Based on these results, we propose an enhanced DM which gives promising results for these difficult scheduling problems. Our results also yield interesting insights into the strengths and limitations of DMs. Copyright © 2000 John Wiley & Sons, Ltd. <s> BIB012 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> The purpose of this study is to develop effective scheduling methodologies for the shop scheduling problem of a flow line. The flow line consists of two machines where only the second machine has separable, external, and sequence-dependent set-up times. The length of set-up times required for a job depends not on the immediately preceding job but on the job which is n steps prior to it. The problem is solved by a dynamic programming with the objective of minimizing the make span. An optimal schedule is found utilizing the sequence dominance condition. Since the computational requirements of the dynamic programming are impracticably demanding for large-sized problems, a genetic algorithm is developed and its performance is examined through a comparative study. <s> BIB013 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> Flow-shop problems with a single server are generalizations of classical flow-shop problems. Immediately before processing, each operation must be loaded onto the corresponding machine, which takes a certain setup time. These setup times are assumed to be separable from the processing times, i.e. a setup on a subsequent machine may be performed while the job is still processed on the preceding machine. All setups have to be done by a single server which can perform at most one setup at a time. New complexity results are derived for special cases. <s> BIB014 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> Abstract This paper presents two mixed-integer linear programming (MILP) models (referred to as WST and SGST in the paper) for a family of four different M-machine, N -job flowshop sequencing problems. Each model may be used to solve the regular, no intermediate queues (NIQ), sequence-dependent setup times (SDST), and SDST/NIQ flowshop problems. The optimal job sequence, based on minimizing makespan, is achieved by a positional assignment approach in the WST model, and by pairs of disjunctive (either–or) constraints in the SGST model. A 12-cell experimental design was used to compare the solution times of the two models for each of the four flowshop problems. The WST model used significantly less computer time than the SGST model for all problem sizes in the regular, NIQ, and SDST flowshop problems. Both models were competitive in the SDST/NIQ flowshop for N ⩽7, but the WST model proved significantly better for N ⩾8. <s> BIB015 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> This paper addresses the problem of improving the polyhedral representation of a certain class of machine scheduling problems. Despite the poor polyhedral representation of many such problems in general, it is shown that notably tighter linear programming representations can be obtained for many important models. In particular, we study the polyhedral structure of two different mixed-integer programming formulations of the flow shop scheduling problem with sequence-dependent setup times, denoted by SDST flow shop. The first is related to the asymmetric traveling salesman problem (ATSP) polytope. The second is less common and is derived from a model proposed by Srikar and Ghosh based on the linear ordering problem (LOP) polytope. The main contribution of this work is the proof that any facet-defining inequality (facet) of either of these polytopes (ATSP and LOP) induces a facet for the corresponding SDST flow shop polyhedron. The immediate benefit of this result is that all developments to date on facets and valid inequalities for both the ATSP and the LOP can be applied directly to the machine scheduling polytope. In addition, valid mixed-integer inequalities based on variable upper-bound flow inequalities for either model are developed as well. The derived cuts are evaluated within a branch-and-cut framework. <s> BIB016 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> Abstract Efficient heuristics for scheduling jobs in a static flowshop with sequence-dependent setup times of jobs are presented in this paper. The objective is to minimize the sum of weighted flowtime and weighted tardiness of jobs. Two heuristic preference relations are used to construct a good heuristic permutation sequence of jobs. Thereafter, an improvement scheme is implemented, once and twice, on the heuristic sequence to enhance the quality of the solution. An existing heuristic, a random search procedure and a greedy local search are used as benchmark methods for relatively evaluating the proposed heuristics. An extensive performance analysis has shown that the proposed heuristics are computationally faster and more effective in yielding solutions of better quality than the benchmark procedures. <s> BIB017 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> Abstract This paper deals with the permutation flowshop scheduling problem in which there are sequence dependent setup times on each machine, commonly known as the SDST flowshop. The optimisation criteria considered is the minimisation of the makespan or C max . Genetic algorithms have been successfully applied to regular flowshops before, and the objective of this paper is to assess their effectiveness in a more realistic and complex environment. We present two advanced genetic algorithms as well as several adaptations of existing advanced metaheuristics that have shown superior performance when applied to regular flowshops. We show a calibration of the genetic algorithm's parameters and operators by means of a Design of Experiments (DOE) approach. For evaluating the proposed algorithms, we have coded several, if not all, known SDST flowshop specific algorithms. All methods are tested against an augmented benchmark based on the instances of Taillard. The results show a clear superiority of the algorithms proposed, especially for the genetic algorithms, regardless of instance type and size. <s> BIB018 </s> A survey of scheduling problems with setup times or costs <s> Flow shop <s> This paper considers the permutation flowshop scheduling problem with sequence-dependent set-up times and develops a penalty-based heuristic algorithm to find an approximately minimum makespan schedule. The proposed algorithm determines the penalty in time associated with a particular sequence and selects the sequence with the minimum time penalty as the best heuristic solution. Computational results comparing the effectiveness and efficiency of the proposed penalty-based heuristic algorithm with an existing savings index heuristic algorithm are reported and discussed. <s> BIB019
Assuming that jobs are ready at time zero, Allahverdi (2000) addressed the F 2=ST si = P f j problem where he obtained optimal (analytical) solutions for certain cases, and established two dominance relations for the general problem. Moreover, he proposed a branch-and-bound algorithm by which problems with up to 35 jobs can be solved optimally in reasonable time. He also proposed three heuristics and compared them with one another. In order to enable end users to be connected to local or remote databases (Intranet/Internet) through the Web, a robust and scalable model is required to provide an interface between the enterprise service and clients. A model that is rapidly spreading uses two separate servers, an application server and a database server. This model is commonly known as the three-tiered architecture. AlAnzi and  showed that the threetiered client-server database internet connectivity problem is equivalent to the F 2=ST si = P f j problem. Therefore, the results of BIB009 can be used for this problem. Moreover, Al-Anzi and  proposed nine additional heuristics for the problem and showed that their proposed heuristics outperform those of BIB009 . Allahverdi and Aldowaisan (2002) also considered the same problem but with the removal times separated from the processing times in addition to setup times, i.e., F 2=ST si ; R si = P f j . They obtained analytically optimal solutions for special cases when the setup, processing and removal times satisfy certain conditions. They also developed dominance relations, a lower bound, and a branch-and-bound algorithm for the general problem. The branchand-bound algorithm yields optimal solutions for up to 35 jobs. Moreover, they proposed different heuristics for the problem. Allahverdi and Al-Anzi (2006a) studied the F 3=ST si = P C j problem. They developed a lower bound, an upper bound, and a dominance relation. Moreover, they presented a branch-and-bound algorithm for the problem, where problems up to 18 jobs can easily be solved. Allahverdi and Al-Anzi (2002) showed that the multimedia data objects scheduling problem for WWW applications can be modeled as F2/ST si / L max . They established dominance relations and proposed four heuristics that outperform the existing ones for the problem. Many dominance relations have been established in the literature for scheduling problems, which are mainly used in implicit enumeration techniques to further reduce the search space for an optimal solution. Al-Anzi and Allahverdi (2006) proposed a novel method for discovering dominance relations for any scheduling problem. After the description of the method, they applied it to the F2/ST si /L max problem. They analyzed the performance of the dominance relations they obtained by the proposed method, as well as the dominance relations proposed earlier including those of Allahverdi and Al-Anzi L max , where the case of negative time lags corresponds to job overlapping which can be used to model the sequence independent setup time problem. They studied polynomial special cases and provided a dominance relation. They also derived lower and upper bounds and presented a branch-andbound algorithm. Al-Anzi and  addressed the Fm/ ST si problem with the objective of minimizing the completion time variance. They presented a hybrid evolutionary heuristic and showed by computational analysis that their heuristic outperforms previous heuristics. BIB001 and Kogan and Levner (1998) studied a special case of the problem F 2 /ST si /C max and used it to describe the scheduling of automated manufacturing cells with computer-controlled transportation robots. They found several solvable cases, when the robotic flow shop problem is reduced to the two-machine flow shop with setup times, and proved that the minimal makespan in such cases can be found efficiently in polynomial time by extending the well-known Johnson algorithm for the classical two-machine flow shop problem. BIB010 addressed the F2/ST si problem with the objective of minimizing a weighted sum of C max and P f j in a dynamic environment, where jobs keep arriving over time. They used a frozenevent procedure to convert the dynamic problem into a static one. They developed an integer programming model and presented a heuristic algorithm with the complexity of O(n 3 ). BIB007 addressed the F2, S/ST si , R si / C max problem for the case where the setup operation is performed by a single server that can perform at most one setup at a time. They addressed the problem under two cases of separable and non-separable setup and removal times. They showed that both cases of the problem are NP-hard in the strong sense. They also proposed some heuristics and analyzed their worst-case error bounds. BIB011 proved the NP-hardness of the same problem in the strong sense without removal times, i.e., F2, S/ST si /C max . BIB014 addressed the Fm, S/ST si /C max problem with m machines and a single server. They derived complexity results for some special cases and showed that some problems are polynomially solvable. For example, they showed the NP-hardness of the F2, S/ST si = s/C max , where ST si = s means that the setup times are the same. BIB014 also considered other objective functions including P C j , P w j C j , P T j , P w j T j , P w j T j , and L max , where they identified some polynomially solvable cases. For example, they showed that the F 2; S=ST si ¼ s= P w j T j is polynomially solvable for the case of equal job processing times. Ríos-Mercado and Bard (1999a,b) addressed the Fm/ST sd /C max problem. Ríos-Mercado and Bard (1999a) presented a branch-and-bound algorithm, incorporating lower and upper bounds and dominance elimination criteria, to solve the problem. They provided test results for a wide range of problem instances. Ríos-Mercado and Bard (1999b) proposed a heuristic for the same problem, which transforms an instance of the problem into an instance of the traveling salesman problem by introducing a cost function that penalizes both large setup times and bad fitness of a given schedule. BIB018 proposed two genetic algorithms for the same problem, and showed that their heuristics outperform that of BIB002 and others. Ruiz and Stü tzle (in press) presented two simple local search based Iterated Greedy algorithms, and showed that their algorithms perform better than those of BIB018 . Ríos-Mercado and Bard (2003) studied the polyhedral structure of two different mixed-integer programming formulations for the same problem. One is related to the asymmetric traveling salesman problem and the other is derived from an earlier proposed model. The two approaches were evaluated by using a branch-and-cut algorithm, which indicated that the approach related to the asymmetric traveling salesman problem was inferior in terms of the computational time. BIB015 also proposed two mixed-integer linear programming models, which are based on the work of  , for the same problem. The mixed-integer programming models proposed by BIB016 and BIB015 were independently developed, and hence, remain to be compared to each other. BIB019 developed a penalty-based heuristic algorithm for the same problem and compared their heuristic with an existing index heuristic algorithm. The Fm/ST sd /C max problem was studied by BIB008 where there exists buffers with finite capacity between machines. He proposed a tabu search based heuristic and compared it with some other methods. Computational experiments showed the effectiveness of the tabu search approach.  addressed the F2/ST sd / C max problem with buffers of zero capacity between the machines, and where some jobs leave after the first machine and some jobs continue through the second machine. They developed lower bounds and presented a heuristic to solve the problem. BIB003 addressed the problem of a side frame press shop in a truck manufacturing company, where all the jobs need to be processed by two machines. All the jobs require processing by the first machine more than once. Moreover, the setup time required by a job on the first machine depends on the two immediately preceding jobs. BIB003 redefined the job elements and converted the problem into the F2/ST sd , prec/ C max problem. They proposed a dynamic programming approach to solve the problem. BIB005 also considered the same problem and presented a genetic algorithm to solve the problem. BIB013 addressed a related problem of F2/ST sd /C max , where the setup times are present only on the second machine and the setup time of a job depends on k (k > 1) immediately preceding jobs. They proposed a dynamic programming formulation and a genetic algorithm for the problem. The Fm=ST sd = P w j f j problem was addressed by BIB004 where they proposed a heuristic for the problem. They also presented an improvement scheme to enhance the quality of the proposed heuristic. BIB006 developed a dynamic programming formulation for the Fm=ST sd = P w j T j problem, where they applied the formulation to a plastic pipe manufacturing factory. They reported that an increase in the number of jobs greatly increases the computational time, while an increase in the number of machines has a very small effect on the computational time of the proposed dynamic programming. BIB017 studied the same problem with a combination of two of the objectives considered by BIB004 and BIB006 , i.e., Fm=ST sd = P w j f j þ P w j T j . BIB017 proposed heuristics and compared them with an existing heuristic, a random search procedure, and a greedy local search. Ruiz and Stü tzle (in press) proposed two simple local search based Iterated Greedy algorithms for the Fm=ST sd = P w j T j problem. They showed that their algorithms perform better than that of BIB017 and earlier heuristics.  addressed the Fm/ST sd , prec problem with the objective of minimizing both C max and n À1 P T i . They proposed a multi-objective genetic algorithm to solve the problem. For the problems considered so far, a job requires only one operation on a machine. In some cases, e.g., in the semiconductor industry, a job may require to have more than one operation on a machine before the job completes its processing on that machine. These flow shops are known as reentrant flow shops. BIB012 addressed the Fm/ST sd /L max problem for a reentrant flow shop. They developed several decomposition methods, and identified an enhanced decomposition method for the problem.