A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> We consider the problem of scheduling two parallel semiautomatic machines sharing the same server for setting up jobs with the objective of minimizing the machine idle time resulting from the unavailability of the server. The problem is shown to be strongly NP-hard and a reduction procedure is developed to transform it into a smaller one with all consecutive job completions alternating between the two machines. In the latter problem, regeneration points are identified for simplifying the idle time computations, leading to the development of an efficient beam search heuristic. Computational results indicate that the beam search performs very favourably when compared with local search on a wide variety of problems. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> We provide a heuristic algorithm for minimizing job earliness and tardiness cost in a multimachine scheduling problem. Our formulation explicitly separates machine setup times from processing times, assumes that setup times may depend on the job-to-job sequence, and assumes that processing times may depend on the job-machine combination. The new algorithm can easily provide approximate solutions to problems involving about 10 machines and 100 jobs when using a personal computer. The accuracy of the solutions was measured using a large variety of problem types taken from the literature. Relative accuracy was measured by comparing the new algorithm's results with those from other heuristics, and absolute accuracy was measured by comparing with results obtained using integer programming methods. The new algorithm was significantly more accurate than the other heuristics, and its average deviation was only about 10% when compared to the optimal solutions. In many cases the new algorithm yielded the optimal so... <s> BIB003 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> Abstract To schedule n jobs on m parallel machines with the minimum total cost is the parallel machine scheduling (PMS) problem. Generally, there is a hypothesis: a job cannot be processed on two machines simultaneously if preemption is allowed. When the processing requirement of a job is considered as the demand of a product, jobs can be split arbitrarily to continuous sublots and processed independently on m machines. So, we can discuss PMS under a hypothesis: any part of a job can be processed on two different machines at the same time, and we call it PMS with splitting jobs. In this paper, we first present some simple cases which are polynomial solvable. Furthermore, a heuristic ML and its worst-case analysis are shown for P / split / C max with independent job setup times. The worst-case performance ratio of ML is within 7 4 −1/m (m⩾2) . <s> BIB004 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> This paper considers the nonpreemptive scheduling of a given set of jobs on several identical, parallel machines. Each job must be processed on one of the machines. Prior to processing, a job must be loaded (setup) by a single server onto the relevant machine. The paper considers a number of classical scheduling objectives in this environment, under a variety of assumptions about setup and processing times. For each problem considered, the intention is to provide either a polynomial- or pseudo-polynomial-time algorithm, or a proof of binary or unary NP-completeness. The results provide a mapping of the computational complexity of these problems. <s> BIB005 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <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> BIB006 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> Abstract We developed a mixed integer programming formulation for minimizing job earliness and tardiness (ET) in a multi-machine scheduling problem. Our formulation allows setup times to depend on the job-to-job sequence, processing times to depend on the job–machine combination, due dates and cost penalties to vary for each job, and machine characteristics to be non-uniform. The model can easily provide the optimal solution to problems involving about nine jobs and three machines. Thus, the formulation shown here can provide the optimal solutions necessary for the development and validation of industrial-scale, multi-machine ET heuristics, which to date, have only been tested against other heuristics. <s> BIB007 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> We present complexity results which have influence on the strength of list scheduling in a parallel machine environment where additional precedence constraints and sequence-dependent setup times are given and the makespan has to be minimized. We show that contrary to various other scheduling problems, in this environment a set of dominant schedules cannot be calculated efficiently with list scheduling techniques. <s> BIB008 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> Abstract In this note we consider the problem of scheduling a set of jobs on m identical parallel machines. For each job, a setup has to be done by a single server. The objective is to minimize the sum of the completion times in the case of unit setup times and arbitrary processing times. For this strongly NP-hard problem, we give a heuristic algorithm with an absolute error bounded by the product of the number of short jobs (with processing times less than m−1 ) and m−2 . <s> BIB009 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem. <s> BIB010 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> Abstract This article proposes lower bounds, as well as a divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times (MSPS). The heuristic is tested on randomly generated instances and compared with a previously published tabu search algorithm. Results show that the proposed heuristic is much faster than tabu search while providing similar quality solutions. <s> BIB011 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> In many manufacturing environments, multiple processing stations are used in parallel to obtain adequate capacity. Likewise, in many production environments, set-up activities are required for switching between items. This work addresses scheduling in parallel machines with sequence dependent set-up times and possibly non-zero ready times with the goal of minimizing makespan. Non-zero ready times allow for application in a continuous planning environment and will also support the expansion of the current model to a multistage production environment. An integer programming formulation is presented. Several heuristics, including approaches based on MULTI-FIT, genetic algorithms and the travelling salesman problem, are then developed and compared empirically. Seven factors are identified in order to generate problem data, including the number of parallel machines, the average number of jobs per machine, set-up time distribution parameters and processing time distribution parameters. The set-up time matrix ca... <s> BIB012 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> Abstract This paper addresses the problem of scheduling a set of independent jobs on unrelated parallel machines with job sequence dependent setup times so as to minimize a weighted mean completion time. The study of the problem stemmed from a real service industry problem. This problem is at least NP-hard in the ordinary sense, even when there are only two identical machines with no setups. Seven heuristic algorithms are proposed and tested by simulation. The results and analysis of quite extensive computational experiments are reported and discussed. The findings through the computational results are presented. Whether this problem is strongly NP-hard is left as an open question. <s> BIB013 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> This paper considers the deterministic problem of scheduling two-operation non-preemptable jobs on two identical semi-automatic machines. A single server is available to carry out the first (or setup) operation. The second operation is executed automatically, without the server. The general problem of makespan minimization is NP-hard in the strong sense. Two special cases which arise in practice, the equal processing times and regular equal setup times problems turn out to be closely linked to the restricted set partitioning problem. This link is used to show that they are NP-hard in the ordinary sense, and to construct a tight lower bound and two highly effective O(n log n) heuristics. <s> BIB014 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-independent setup times <s> This paper considers the problem of scheduling two-operation non-preemptable jobs on two identical semi-automatic machines. A single server is available to carry out the first (or setup) operation. The second operation is executed automatically, without the server. The general problem of makespan minimization is NP-hard in the strong sense. In earlier work, we showed that the equal total length problem is polynomial time and we also provided efficient and effective solutions for the special cases of equal setup and equal processing times. Most of the cases analyzed thus far have fallen into the category of regular problems. In this paper we build on this earlier work to deal with the general case. Various approaches will be considered. One may reduce the problem to a regular one by amalgamating jobs, or we may apply the earlier heuristics to (possibly regular) job clusters. Alternately we may apply a greedy heuristic, a metaheuristic such as a genetic algorithm or the well known Gilmore-Gomory algorithm to solve the general problem. We report on the performance of these various methods. <s> BIB015
There is no need to consider non-batch sequenceindependent setup times for the general parallel machine problem since the setup times can be included in the processing times. However, for certain parallel machine problems, the setup times should be considered as separate from the processing times. It is assumed that a job can be processed by at most one machine at a time for the general parallel machine problem. BIB004 considered the case where a job can be processed on two different machines at the same time. For this problem, BIB004 presented a heuristic with a worst-case performance ratio of 7/4 À 1/m (m P 2) when the objective function is C max and the jobs have sequence-independent setup times. Assuming that a setup is required each time a job is preempted,  proposed an approximation algorithm for the P/ ST si , pmtn/C max problem, where the worst case ratio of the algorithm can be made arbitrarily close to 4/ 3. They also demonstrated the existence of a polynomial-algorithm for the case of equal setup times. The following parallel machine scheduling problem has recently been addressed in the literature. There is a set of n jobs to be processed on a set of m parallel machines. The loading of a job on a machine, the time of which is called the setup time, is performed by a single server. This setup time cannot be performed while a machine is processing a job. On the other hand, the machine can process a job without the server being present after the job is loaded on the machine. Simultaneous requests of the server by the machines will result in machine idle time. This problem is denoted as P,S/ST si /c. When the setup time is constant for each job it is denoted as ST si = s. BIB002 studied the P, S/ ST si = s/C max problem and showed that it is strongly NP-hard. They analyzed some list scheduling heuristics for the problem and presented some polynomially solvable cases. BIB009 considered the same problem but with unit setup times and the total completion time criterion, i.e., P ; S=ST si ¼ 1= P C j . They presented a heuristic algorithm and proved that the heuristic has an absolute error bounded by the product of the number of short jobs (with processing times less than m À 1) and m À 2. BIB010 addressed the P ; S=ST si = P w j C j problem and presented a (5 À 1/m) approximation algorithm, which is based on a linear relaxation. They also showed that the SPT (Shortest Processing Time) schedule is a 3/2 approximation for the P ; The problem was also addressed for the case of two parallel machines. BIB001 showed that the P2, S/ST si problem with the objective of minimizing the machine idle time resulting from unavailability of the server is NP-hard in the strong sense. He proposed an efficient beam search heuristic for the problem.  addressed the P2, S/ST si /C max problem under a specific assumption of alternating job processing, the definition of which was not precisely given. They proved the strong NP-hardness of the problem, suggested an integer programming formulation, and presented polynomial algorithms for several more restricted cases. BIB014 considered the same problem, but for the special cases of equal processing and setup times. They proved the NP-hardness of two special cases of the same problem, and proposed heuristics for each case. BIB015 also considered the same problem for the general case. They proposed greedy heuristics and a genetic algorithm for the general case. They also proposed the use of the well-known Gilmore-Gomory algorithm to solve the general case. BIB005 proved the strong NP-hardness of the problems P2, S/ST si with C max and P C j objectives for the case where the setup times are all equal. If all the job processing times are one unit, then the problem P2, S/ST si with the objectives BIB001 Minimizing machine idle timeresulting from unavailability of the server (setup is performed by a single server, only two machines) NP-hard in the strong sense, beam search heuristic BIB002 C max , minimizing the amount of time in list scheduling when some machine is idle due to the unavailability of the server (setup is performed by a single server) Strongly NP-hard for C max , and the strongly NP-hard for the forced idle time even when setup times are constant, polynomially solvable cases, heuristics  C max (setup is performed by m À 1 servers) A pseudo-polynomial algorithm  C max (preemption) Algorithm, worst case ratio BIB006 C max (setup is performed by a single server, dedicated machines) NP-hard even for special cases, polynomially solvable cases, algorithms, worst-case ratio BIB005 C max , L max , Proofs of binary or strongly NPcompleteness, polynomial or pseudopolynomial-time algorithms BIB004 C max (a job may be processed on two different machines simultaneously) Heuristic, worst-case performance ratio  New complexity results for special cases BIB014 C max (setup is performed by a single server, only two machines, equal setup times) Complexity results, lower bound, heuristics BIB003 Earliness cost + tardiness cost (some machines may not process some jobs) Mixed integer programming, Bender's decomposition procedure (for larger problems) Sivrikaya-Serifoglu and Ulusoy (1999)  Mixed integer programming, simulated annealing BIB007 P w j E j þ P w j T j (R) Mixed integer programming BIB011 C max Lower bounds, heuristic BIB008 C max (precedence constraints) Complexity results BIB012 C max (r j ) Integer programming, traveling salesman problem, genetic algorithm, multi-fit BIB013 P w j C j ðRÞ Seven heuristics are proposed and evaluated (continued on next page) P T j and P w j U j is NP-hard, with the objective P w j T j is strongly NP-hard, and the problem P,S/ ST si with the objectives C max , L max , P C j , P w j C j and P U j is polynomially solvable. The questions about the NP-hardness of the problem P ; S=ST si = P C j and the strong NP-hardness of the problem P 2; S=ST si = P w j C j were left open. The first question was answered by  , who proved the strong NP-hardness of the problem P ; S=ST si = P C j . Brucker et al. derived numerous complexity results for the server scheduling problems in the parallel machine environment. They made and proved an observation that several classical single and parallel machine scheduling problems polynomially reduce to their server counterparts. The NP-hardness of a number of server scheduling problems readily follows from this reduction. They developed an O(n 7 ) algorithm for the problem P 3; S=ST si = P C j with unit setup times and a number of polynomial algorithms for the special cases with equal setup times and equal processing times. The complexity of the problem Pm; S=ST si = P C j with given m P 4 has remained unsolved.  presented more complexity results for the problem. Another comprehensive paper was by BIB006 , who addressed the same problem with the C max objective function but with dedicated machines, where each machine processes its own set of pre-assigned jobs. In other words, the set of n jobs is in advance split into m subsets, where all the jobs in a subset are performed by the same machine. They proved that the problem with two dedicated machines is NP-hard in the strong sense even if all the setup times are equal or if all the processing times are equal. They showed that a simple greedy algorithm creates a schedule that is at most twice the optimal value for the case of m machines. They also presented a heuristic with a worst-case ratio of 3/2 for the case of two machines. In all of the above mentioned research, the setup times were assumed to be performed by a single server.  considered the problem with m À 1 servers where there are m machines. They presented a pseudo-polynomial time algorithm for the problem when the objective is to minimize C max . 