A survey of scheduling problems with setup times or costs <s> Others <s> Abstract In this paper we apply the tabu search (TS) technique to a complex machine scheduling problem. The problem can be considered as a generalization of the job-shop problem with both simple and parallel machines, job batches, setup times and release and due dates. The goal is to obtain feasible schedules by minimizing the makespan Cm,, if the problem is feasible, or to obtain a “best compromise” schedule if a full solution is not possible. The TS algorithm developed here is distinguished mainly by two aspects. Firstly, the core of the procedure is a tabu thresholding algorithm which uses a sophisticated set of moves aimed at resolving violated constraints. Secondly, the TS algorithm supplements the central tabu thresholding algorithm with two diversification strategies which are dependent on the state of the search. These strategies involve fairly major disruption of the schedules, and force significant diversification of the search. Computational experiments show that our algorithm can find high quality schedules in short running times <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Others <s> A two-phase procedure for configuring a cellular manufacturing system is proposed. In Phase I, a new similarity coefficient which considers the number of alternative routes when available during machine failure is proposed. The objective of Phase I is to identify part families based on the proposed new similarity coefficient. In Phase II, a new methodology which simultaneously considers scheduling and operational aspects in the cell design during machine failure for a manufacturing environment is proposed. Phase II shows how the scheduling and operational aspects influence the resource utilization during machine failure. The objective of the proposed methodology is to minimize the total sum of inventory holding cost, early/late finish penalty cost for each part in a given period, operating cost and machine investment cost by grouping machines into cells. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Others <s> We study four scheduling problems involving the maximum lateness criterion and an element of batching. For all the problems that we examine, algorithms appear in the literature that consist of a sorting step to determine an optimal job sequence, followed by a dynamic programming step that determines the optimal batches. In each case, the dynamic program is based on a backward recursion of which a straightforward implementation requires O(n^2) time, where n is the number of jobs. We present improved implementations of these dynamic programs that are based on monotonicity properties of the objective expressed as a function of the total processing time of the first batch. These properties and the use of efficient data structures enable optimal solutions to be found for each of the four problems in O(nlogn) time; in two cases, the batching step is actually performed in linear time and the overall complexity is determined by the sorting step. <s> BIB003 </s> A survey of scheduling problems with setup times or costs <s> Others <s> This study investigates the performance of order-input sequencing heuristics in a cellular flexible assembly system (CFAS) by computer simulation. The CFAS produces low-volume, large products in an assemble-to-order environment. This study examines two types of heuristic: two-stage (group scheduling) heuristics and single-stage heuristics. Two-stage heuristics attempt to serially process similar orders and eliminate major setups required between subfamilies. The results of the paired t -test analysis show that the two-stage heuristics outperform the single-stage heuristics under each experimental condition for various measures. The superior performance of the two-stage heuristics is due to the reduction in major setup times. The simulation results can provide guidance for schedulers in the selection of preferable heuristics for relevant CFASs. <s> BIB004 </s> A survey of scheduling problems with setup times or costs <s> Others <s> This paper considers the scheduling problem to minimize total tardiness given multiple machines, ready times, sequence dependent setups, machine downtime and scarce tools. We develop a genetic algorithm based on random keys representation, elitist reproduction, Bernoulli crossover and immigration type mutation. Convergence of the algorithm is proved. We present computational results on data sets from the auto industry. To demonstrate robustness of the approach, problems from the literature of different structure are solved by essentially the same algorithm. <s> BIB005 </s> A survey of scheduling problems with setup times or costs <s> Others <s> The Wafer Probing Scheduling Problem (WPSP) is a practical generalization of the parallel-machine scheduling problem, which has many real-world applications, particularly, in the Integrated Circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which must be processed on groups of identical parallel machines and be completed before the due dates. The job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequentially dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this paper, we consider the WPSP and formulate the WPSP as an integer programming problem to minimize the total machine workload. We demonstrate the applicability of the integer programming model by solving a real-world example taken from a wafer probing shop floor in an IC manufacturing factory. <s> BIB006 </s> A survey of scheduling problems with setup times or costs <s> Others <s> The wafer probing scheduling problem (WPSP) is a variation of the parallel-machine scheduling problem, which has many real-world applications, particularly, in the integrated circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which must be processed on groups of identical parallel machines and be completed before the due dates. Further, the job processing time depends on the product type, and the machine setup time is sequence dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequence dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this paper, we formulate the WPSP as an integer programming problem. We also transform the WPSP into the vehicle routing problem with time windows (VRPTW), a well-known network routing problem which has been investigated extensively. An illustrative example is given to demonstrate the proposed transformation. Based on the provided transformation, we present three efficient algorithms to solve the WPSP near-optimally. <s> BIB007 </s> A survey of scheduling problems with setup times or costs <s> Others <s> This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical decomposition of the planning process into distinct optimization subproblems, addressing issues such as the assignment of board types to machine groups, the allocation of component feeders to individual machines, the determination of optimal production sequences, etc. The paper reviews the literature on this topic with an emphasis on the most recent developments, on the fundamental structure of the mathematical models and on the relation between these models and some 'environmental' variables such as the layout of the shop or the product mix. <s> BIB008 </s> A survey of scheduling problems with setup times or costs <s> Others <s> Increases in the demand for integrated circuits have highlighted the importance of meeting customer quality and on-time delivery expectations in the semiconductor industry. A modified shifting bottleneck heuristic is developed for minimizing the total weighted tardiness in a semiconductor wafer fabrication facility. This ‘complex’ job shop is characterized by re-entrant or re-circulating product flow through a number of different tool groups (one or more machines operating in parallel). These tool groups typically contain batching machines, as well as machines that are subject to sequence-dependent setups. The disjunctive graph of the complex job shop is presented, along with a description of the proposed heuristic. Preliminary results indicate the heuristic's potential for promoting on-time deliveries by semiconductor manufacturers for their customers' orders. Copyright © 2002 John Wiley & Sons, Ltd. <s> BIB009 </s> A survey of scheduling problems with setup times or costs <s> Others <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> BIB010 </s> A survey of scheduling problems with setup times or costs <s> Others <s> We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem. This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup times are equal and there are two ditstinct due dates. This problem is solved in O(n3) time when all job processing times on the first machine are equal, and it is solved in O(n4) time when all processing times on the second machine are equal. <s> BIB011 </s> A survey of scheduling problems with setup times or costs <s> Others <s> Abstract The frequent changeovers in the production processes indicate the importance of setup time in many real-world manufacturing activities. The traditional approaches in dealing with setup times are that either to omit or to merge into the processing times so as to simplify the problems. These approaches could reduce the complexity of the problem, but often generated unrealistic outcomes because of the assumed conditions. This situation motivated us to consider sequence-dependent setup times in a real-world BOPP film scheduling problem. First, a setup time-based heuristic method was developed to generate the initial solutions for the genetic algorithms (GAs). Then, genetic algorithms with different mutation methods were applied. Extensive experimental results showed that the setup time-based heuristic method was relatively efficient. It was also found that a genetic algorithm with the variable mutation rate performed much effectively than one with the fixed mutation rate. <s> BIB012 </s> A survey of scheduling problems with setup times or costs <s> Others <s> One-operator two-machine open shop and flow shop problems are 𝒩𝒫-hard in the ordinary sense even if all the weights are the same. We discuss two different pseudo polynomial dynamic programming recursions for each of the open shop and flow shop case. Some of the running times are better than those of the best known algorithms in the literature. †E-mail: rvickson@engmail.uwaterloo.ca <s> BIB013 </s> A survey of scheduling problems with setup times or costs <s> Others <s> We consider the processing of M jobs in a flow shop with N stations in which only a single server is in charge of all stations. We demonstrate that for the objective of minimizing the total setup and holding cost, a class of easily implementable schedules is asymptotically optimal. <s> BIB014 </s> A survey of scheduling problems with setup times or costs <s> Others <s> In this paper, we consider the wafer probing scheduling problem (WPSP) to sequence families of jobs on identical parallel machines with due date restrictions. The machine set-up time is sequentially dependent on the product types of the jobs processed on the machine. The objective is to minimize the total machine workload without violating the machine capacity and job due date restrictions. The WPSP is a variation of the classical parallel-machine scheduling problem, that can be transformed into the vehicle-routing problem with time windows (VRPTW). One can therefore solve the WPSP efficiently using existing VRPTW algorithms. We apply four existing savings algorithms presented in the literature including sequential, parallel, generalized, and matching based savings, and develop three modifications called the modified sequential, the compound matching based, and the modified compound matching-based savings algorithms, to solve the WPSP. Based on the characteristics of the wafer probing process, a set of test problems is generated for testing purposes. Computational results show that the three proposed modified algorithms perform remarkably well. <s> BIB015 </s> A survey of scheduling problems with setup times or costs <s> Others <s> Abstract The integrated-circuit final testing scheduling problem (ICFTSP) with reentry is a variation of the complex flow-shop scheduling problem, which is also a generalization of the classical reentrant flow batch process problem, and the identical parallel machine problem. In this paper, we present a case study on the ICFTSP with reentry, which is taken from a final testing shop floor in an integrated circuit manufacturing factory. For the case investigated, the jobs are clustered by their product types, which must be processed on groups of parallel machines at various process stages following the manufacturing sequence, which must be completed before the due dates. The job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. The objective is to schedule jobs without violating all constraints, while the total machine workload is minimized. Since the ICFTSP has reentry characteristic, and involves job processing precedence, serial-processing stage, batch-processing stage, job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequence dependent setup time, it is more difficult to solve than the classical flow-shop scheduling problem. We present three fast network algorithms to efficiently solve the ICFTSP with reentry and provide a performance comparison between the three algorithms on eight test problems. <s> BIB016 </s> A survey of scheduling problems with setup times or costs <s> Others <s> This research focuses on solving a common wafer test scheduling problem in semiconductor manufacturing. During wafer testing, a series of test processes are conducted on wafers using computer-controlled test stations at various temperatures. The test processes are conducted in a specified order on a wafer lot, resulting in precedence constraints for the schedule. Furthermore, the assignment of the wafer lots to test stations and the sequence in which they are processed affects the time required to set up the test operations. Thus, the set-up times are sequence dependent. Four heuristics are developed to solve the test scheduling problem with the aim of minimizing the makespan required to test all wafers on a set of test stations. The heuristics generate a sorted list of wafer lots as a dispatching sequence and then schedule the wafer lots on test stations in order of appearance on the list. An experimental analysis and two case studies are presented to validate the proposed solution approaches. In the cas... <s> BIB017 </s> A survey of scheduling problems with setup times or costs <s> Others <s> Abstract The scheduling problem of n printed circuit boards (PCBs) for m non-identical parallel machines is considered in this paper. The problem has to deal with three issues: (i) classifying the PCBs into m groups corresponding to m machines, (ii) sequencing the boards for each machine, and (iii) component switching (component unloading/loading) from the machine magazine. A general objective is to minimize the total makespan, which is shown here to be the same as minimizing the maximum of number of component switches. The complete problem is complex, and is usually dealt in stages, which may not yield a good solution. We model the problem in an integrated manner using weighted multiple objectives to deal with grouping of the boards, load balancing at each machine, board sequencing and component switching at a machine. A composite genetic algorithm is developed to solve this multi-objective problem. The integrated solution is encoded as a string of pair values for each group of boards. The first number indicates the board membership in a group, and the second one represents the sequencing position of a board in that group. A new population of solutions is generated by using both binary genetic operators for grouping and genetic operators for board sequencing. A fitness function evaluates workload balancing, board similarities and total setup time simultaneously. Experiments are designed and run to test the proposed methodology, and the results show that the solutions are efficient, and are obtained within a reasonable amount of time. <s> BIB018 </s> A survey of scheduling problems with setup times or costs <s> Others <s> This paper addresses the m-machine no-wait flowshop problem where the set-up time of a job is separated from its processing time. The performance measures considered are the total flowtime and makespan. The scheduling problem for makespan reduces to the travelling salesman problem (TSP), and the scheduling problem for total flowtime reduces to the time-dependent travelling salesman problem (TDTSP). Non-polynomial time solution methods are presented, along with a polynomial heuristic. <s> BIB019 </s> A survey of scheduling problems with setup times or costs <s> Others <s> Consider the two-machine no-wait flowshop problem where the setup and removal times of a job at each machine are separated from the processing time. The scheduling objective is to minimize the sum of the total flowtime. Two optimization properties are first developed. In view of the NP-hard of this problem, optimal solutions seem unnecessary especially when the number of jobs is large. Then, combined the developed optimization properties with the greedy search a heuristic algorithm is developed. Computational experience demonstrates the effectiveness of the heuristic algorithm in finding near optimal schedules. <s> BIB020 </s> A survey of scheduling problems with setup times or costs <s> Others <s> This paper studies the two-stage no-wait hybrid flowshop scheduling problem where one of the two stages consists of several identical parallel machines and the setup and removal times of each job at each stage are separated from the processing time. In view of the NP-complete of this problem, heuristic algorithms regarding sequencing and assigning of jobs to each stage as independent procedure are proposed. Two theorems are also proposed for sequencing job procedure. Computational experience demonstrates the effectiveness of the heuristic algorithm including the proposed theorems in finding a near optimal schedule. <s> BIB021
Baki BIB010 BIB013 and BIB011 studied a two-machine flow shop problem in which the processing of the jobs requires the continuous presence of a single operator. The operator can serve one machine at a time and there is a machine dependent setup time when it switches to a particular machine. BIB010 derived an O(n log n) time algorithm to minimize L max . BIB013 and BIB011 proved the NP-hardness of minimizing P U j , and suggested pseudopolynomial-time algorithms for minimizing P w j U j . BIB011 showed a relationship of the flow shop problem and a single machine single family batch scheduling problem, which leads to the following results: O(n log n) time algorithms for minimizing L max and for minimizing P C j in the case of agreeable processing times, strong NP-hardness of minimizing P w j C j , and dynamic programming algorithms for minimizing P w j U j . BIB010 also studied a single operator problem in the two-machine open shop environment. The problem is equivalent to the problem 1/ST si,b /L max with two families, and can be solved in O(n log n) time by the algorithm of BIB003 . BIB014 considered an m-machine flow shop in which the processing times are machine dependent, and there are machine dependent setup costs and holding costs for a job to stay one time unit on a machine. The objective is to minimize the total setup and holding cost. They introduced a so-called chain-like structure schedule, and proved that such a schedule is asymptotically optimal as n ! 1. They also proved that any algorithm in a natural class of algorithms is a 2-approximation algorithm for the considered problem. BIB001 addressed the problem of a machine workshop in a Spanish company that produces heavy boat engines and electricity power stations. The problem is a generalization of the job shop scheduling problem, where in some stations there is more than one machine and the machines need to be set up if the coming job is in a different family. Each job has a release date and a due date. The objective is to minimize the makespan. BIB001 proposed a tabu search algorithm to solve the problem. BIB004 studied cellular flexible assembly systems that produce low-volume, large products in an assemble-to-order environment such as the assembly of weapons and heavy machinery. Leu proposed two heuristics, namely a single-stage and two-stage heuristics. The two-stage heuristic attempts to serially process similar orders and eliminate the major setup times required between different families. The two-stage heuristic was statistically shown to perform better than the single-stage heuristic with respect to different measures.  studied the same problem in a hybrid order shipment environment. They proposed a singlestage heuristic and a two-stage heuristic, and showed by computational experiments that the two-stage heuristic outperforms the single-stage heuristic. Norman and Bean (1999) investigated a scheduling problem that arises from an automaker. They stated that there are many factors that complicate such a problem. Among them, there are different job release and due dates that range throughout the study of the horizon. Moreover, each job has a particular tooling requirement, and tooling conflicts may arise since there is only one copy of each tool and several jobs may require the same tool. Also, the setup times are sequence dependent and the machines are not identical. BIB005 proposed a genetic algorithm for the problem, proved its convergence and tested its performance on data sets obtained from the auto industry. Pearn et al. (2002a,b) and  considered a scheduling problem in wafer probing factories. In these factories, jobs are clustered by their product types and must be completed before their due dates. The setup times are sequence dependent. Pearn et al. (2002a,b) and  considered the problem to find a schedule that minimizes the total setup time. BIB006 and  formulated the problem as an integer programming problem, and BIB007 transformed it into the vehicle routing problem with time windows. BIB007 also presented three heuristic algorithms with job insertions for the problem. BIB015 considered the same problem and computationally tested four existing so called ''saving'' vehicle-routing heuristics and three new modifications. The tests demonstrated high efficiency of the modified heuristics. The idea of a saving heuristic is to insert pairs of jobs based on their setup time characteristic called saving. Saving of a pair of jobs includes three setup times: two setup times assuming that the jobs are the first and the last jobs in the schedule and a setup time between the jobs of the pair. BIB016 addressed the integrated-circuit final testing scheduling problem with reentry of some operations with the same objective function of minimizing the total machine workload. They presented three fast network heuristic algorithms for solving the problem. BIB017 addressed the wafer test scheduling problem with the objective of minimizing makespan. They stated that the jobs have precedence constraints because the test processes are conducted in a specified order on a wafer lot, and setup times are sequence-dependent. They proposed four heuristics for the problem, and applied the heuristics to actual data from a semiconductor manufacturing facility. The results showed that the makespan is reduced by 23-45%. BIB008 surveyed the literature on the printed circuit board assembly planning problems with an emphasis on the classification of the related mathematical models. The general models they considered include the simultaneous production sequencing with family setups, an assignment of setup facilities, and determination of setup policies. BIB009 addressed a scheduling problem in semiconductor wafer fabrication facility, where the facility is described as a complex job shop with reentrant flow of products, batching machines, and sequence-dependent setup times. They proposed a modified shifting bottleneck heuristic for the problem to minimize the total weighted tardiness. Van BIB018 considered the printed circuit boards (PCB) problem. They stated that the problem has three subproblems which are (i) classifying the PCBs into m groups, where m is the number of available machines, (ii) finding the sequence for each machine, and (iii) component switching, which includes the setup operations. They proposed a genetic algorithm to solve the problem with the objective of minimizing the makespan, which was shown to be the same as minimizing the maximum number of component switches. BIB002 proposed and evaluated a number of strategies for operating a single printed circuit board assembly machine. The strategy adapting the group technology principle was shown to be applicable when component commonality is high and changeovers are time consuming. Partial setup strategies, which allow product families to be split and focus on minimizing the total production time, are shown to adapt to changing production conditions and therefore outperform the other setup strategies. BIB012 considered a biaxially oriented polypropylene (BOPP) film factory, which produces products such as adhesive tapes, photo albums, foodstuff packages, book covers, etc., where the job setup times are sequence-dependent. They proposed a genetic algorithm with variable mutation rates for the problem, and showed that the algorithm outperforms the current practice in the factory. Queues of tow/barges form when a river lock is rendered inoperable due to several reasons including lock malfunction, a tow/barge accident, and adverse lock operating conditions. Nauss (in press) developed model formulations that allow queues of tow/barges to be cleared using a number of differing objectives in the presence of different setup times between successive passages of tow/barges through the lock. He presented linear and nonlinear integer programming formulations, and carried out computational experiments on a representative set of the problems, showing that the solution approaches generate improved solutions over the current practice. Aubry et al. (in press ) addressed the problem of minimizing the setup costs of a workshop modeled with parallel multi-purpose machines by ensuring that a load-balanced schedule exists. They showed that the problem is NP-hard in the strong sense, and presented the problem as a mixed integer linear program. They also showed that the problem in certain cases can be stated as a transportation problem. Monkman et al. (in press ) proposed a heuristic for a production scheduling problem at a high volume assemble-to-order electronics manufacturer. The proposed heuristic involves assignment, sequencing, and time scheduling steps, with an optimization approach developed for each step. They compared the setup costs resulting from the use of the proposed heuristic against a heuristic previously developed and implemented at the electronics manufacturer. A reduction of setup costs, about 20%, was achieved by applying the proposed heuristic. Havill and Mao (in press) studied the problem of scheduling online perfectly malleable parallel jobs with arbitrary times on two or more machines. They  Simulation, optimization, heuristics, simulated annealing BIB019 m (no-wait) C max , P f j Non-polynomial time solution methods, heuristic BIB020 2 (no-wait) P f j (R si ) Dominance relations, heuristic BIB021 2 (Flexible and no-wait) Multi-objective genetic algorithm took into account the setup time to create, dispatch, and destroy multiple processes. They presented an algorithm to minimize makespan. Yokoyama (in press) described a scheduling model for a production system including machining, setup and assembly operations. Production of a number of single-item products is ordered. Each product is made by assembling a set of several different parts. First, the parts are produced in a flowshop consisting of m machines. Then, they are assembled into products on a single assembly stage. Setup time is needed when a machine starts processing the parts or it changes items. The objective function is the mean completion time for all the products. The author proposed solution procedures using pseudo-dynamic programming and a branchand-bound algorithm. Mika et al. (in press ) addressed the multi-mode resource-constrained project scheduling problem with schedule-dependent setup times. A scheduledependent setup time is defined as a setup time dependent on the assignment of resources to activities over time, when resources are, e.g., placed in different locations. In such a case, the time necessary to prepare the required resource for processing an activity depends not only on the sequence of activities but, more generally, on the locations in which successive activities are executed. They proposed a tabu search heuristic to solve the problem.