A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> Abstract This paper considers the problem of scheduling part families and jobs within each part family in a flowline manufacturing cell where the setup times for each family are sequence dependent and it is desired to minimize the makespan while processing parts (jobs) in each family together. Lower bounds on the optimal makespan value and efficient heuristic algorithms for finding permutation schedules are proposed and empirically evaluated as to their effectiveness in finding optimal permutation schedules. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> This paper presents development of a scheduling system for Thin Film Transistor Liquid Crystal Display (TFT LCD) assembly process. With given daily production plan that is rough-cut capacitated, the scheduler generates shift-based capacity feasible schedules at each assembly step. The scheduling problem is a parallel-machine scheduling problem with sequence dependent setups and some manufacturing environments, which make the problem considerably difficult. The scheduling objective is to minimize the mean flow time and maximize the production progressiveness. Two scheduling heuristics are proposed for each production step of assembly process. The first scheduling heuristic is applicable for the first three steps of assembly process, i.e. coating, rubbing, and attaching step, and for the later steps another similar heuristic is employed. We also propose a simple method for computing production requirements for each step where daily production demand is unknown. The proposed scheduling procedures are implemented in a real TFT LCD manufacturing line and their performances are investigated. The experimental results show that the proposed scheduler provides quite better schedules than the current practice employed in the line in terms of both mean flow time and fulfillment of production demands. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> Abstract This paper presents several search heuristics and their performance in batch scheduling of parallel, unrelated machines. Identical or similar jobs are typically processed in batches in order to decrease setup times and/or processing times. The problem accounts for allotting batched work parts into unrelated parallel machines, where each batch consists of a fixed number of jobs. Some batches may contain different jobs but all jobs within each batch should have an identical processing time and a common due date. Processing time of each job of a batch is determined according to the machine group as well as the batch group to which the job belongs. Major or minor setup times are required between two subsequent batches depending on batch sequence but are independent of machines. The objective of our study is to minimize the total weighted tardiness for the unrelated parallel machine scheduling. Four search heuristics are proposed to address the problem, namely (1) the earliest weighted due date, (2) the shortest weighted processing time, (3) the two-level batch scheduling heuristic, and (4) the simulated annealing method. These proposed local search heuristics are tested through computational experiments with data from dicing operations of a compound semiconductor manufacturing facility. <s> BIB003 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> In this paper, we consider a simplified real-life identical parallel machine scheduling problem with sequence-dependent setup times and job splitting to minimize makespan. We propose a heuristic to solve this problem. Our method is composed of two parts. The problem is first reduced into a single machine scheduling problem with sequence-dependent setup times. This reduced problem can be transformed into a Traveling Salesman Problem (TSP), which can be efficiently solved using Little's method. In the second part, a feasible initial solution to the original problem is obtained by exploiting the results of the first part. This initial solution is then improved in a step by step manner, taking into account the setup times and job splitting. We develop a lower bound and evaluate the performances of our heuristic on a large number of randomly generated instances. The solution given by our heuristic is less than 4.88% from the lower bound. <s> BIB004 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> In many practical manufacturing environments, jobs to be processed can be divided into different families such that a setup is required whenever there is a switch from processing a job of one family to another job of a different family. The time for setup could be sequence independent or sequence dependent. We consider two particular scheduling problems relevant to such situations. In both problems, we are given a set of jobs to be processed on a set of identical parallel machines. The objective of the first problem is to minimize total weighted completion time of jobs, and that of the second problem is to minimize weighted number of tardy jobs. We propose column generation based branch and bound exact solution algorithms for the problems. Computational experiments show that the algorithms are capable of solving both problems of medium size to optimality within reasonable computational time. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 823–840, 2003. <s> BIB005 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> Abstract In this paper we address a scheduling problem taken from a label sticker manufacturing company. The production system is a two-stage hybrid flow shop with the characteristics of sequence-dependent setup time at stage 1, dedicated machines at stage 2, and two due dates. The objective is to schedule one day's mix of label stickers through the shop such that the weighted maximal tardiness is minimized. A heuristic is proposed to find the near-optimal schedule for the problem. The performance of the heuristic is evaluated by comparing its solution with both the optimal solution for small-sized problems and the solution obtained by the scheduling method currently used in the shop. As the heuristic is beneficial to the company, it will be implemented in the near future. <s> BIB006 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> Lot streaming involves splitting a production lot into a number of sublots, in order to allow the overlapping of successive operations, in multi-machine manufacturing systems. In no-wait flowshop scheduling, sublots are necessarily consistent, that is, they remain the same over all machines. The benefits of lot streaming include reductions in lead times and work-in-process, and increases in machine utilization rates. We study the problem of minimizing the makespan in no-wait flowshops producing multiple products with attached setup times, using lot streaming. Our study of the single product problem resolves an open question from the lot streaming literature. The intractable multiple product problem requires finding the optimal number of sublots, sublot sizes, and a product sequence for each machine. We develop a dynamic programming algorithm to generate all the nondominated schedule profiles for each product that are required to formulate the flowshop problem as a generalized traveling salesman problem. This problem is equivalent to a classical traveling salesman problem with a pseudopolynomial number of cities. We develop and computationally test an efficient heuristic for this problem. Our results indicate that solutions can quickly be found for flowshops with up to 10 machines and 50 products. Moreover, the solutions found by our heuristic provide a substantial improvement over previously published results. <s> BIB007 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> This paper presents a preliminary analysis of the typical scheduling environment in semiconductor manufacturing involving multiple job families, and where more than one objective such as cycle time, machine utilization and the due-date accuracy needs to be simultaneously considered. In this study, the NP-hard problem of scheduling N independent jobs on a single testing machine with due dates and sequence-dependent setup times is addressed, where the multiple objectives are to minimize average cycle time, to minimize average tardiness, and to maximize machine utilization. A Pareto optimal solution, which is not inferior to any other feasible solutions in terms of all objectives, is generated combining the analytically optimal and conjunctive simulated scheduling approach. First, the machine-scheduling problem is modeled using the discrete event simulation approach and the problem is divided into simulation clock based lot selection sub-problems. Then, a Pareto optimal lot is selected using the compromise programming technique for multiobjective optimization at each decision instant in simulated time. With the help of a broad experimental design, this developed solution is then compared with common heuristic-dispatching rules such as SPT and EDD, which show better results for all the objectives over a wide range of problems. The developed scheduling method shows approximately 16.7% reduction in average cycle time, 25.6% reduction in average tardiness, and 21.6% improvement in machine utilization over the common dispatching rules, SPT and EDD. <s> BIB008 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> This paper considers the problem of scheduling part families and jobs within each part family in a flowshop manufacturing cell with sequence dependent family setups times where it is desired to minimize the makespan while processing parts (jobs) in each family together. Two evolutionary algorithms-a Genetic Algorithm and a Memetic Algorithm with local search-are proposed and empirically evaluated as to their effectiveness in finding optimal permutation schedules. The proposed algorithms use a compact representation for the solution and a hierarchically structured population where the number of possible neighborhoods is limited by dividing the population into clusters. In comparison to a Multi-Start procedure, solutions obtained by the proposed evolutionary algorithms were very close to the lower bounds for all problem instances. Moreover, the comparison against the previous best algorithm, a heuristic named CMD, indicated a considerable performance improvement. <s> BIB009 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> Abstract This paper addresses the problem of products grouping in the tile industry. This production system can be classified as a three-stage hybrid flowshop with sequence dependent and separable setup times. Main objective has been to identify a set of families integrated by products with common features. This classification would help Production Managers to minimize changeover time, allowing them to further reduce production times. The basic concept of “exploiting similarities”, taken from the Group Technology (GT) philosophy, has been used to address the problem in a creative way. A new “coefficient of similarity” between each of the products, has been defined and used as a parameter, allowing products to be grouped through a heuristic method. This research has already been applied in the framework of a real case, getting quite positive results (actual reduction in both setup and production costs, easier long-horizon planning and short-horizon scheduling, more accurate set up time estimates for new products, etc.). <s> BIB010 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> This paper presents a branch-and-bound (B&B) algorithm for minimizing the sum of completion times in a single-machine scheduling setting with sequence-dependent family setup times. The main feature of the B&B algorithm is a new lower bounding scheme that is based on a network formulation of the problem. With extensive computational tests, we demonstrate that the B&B algorithm can solve problems with up to 60 jobs and 12 families, where setup and processing times are uniformly distributed in various combinations of the [1,50] and [1,100] ranges. <s> BIB011 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> A large dynasearch neighborhood is introduced for the one-machine scheduling problem with sequence-dependent setup times and costs and earliness-tardiness penalties. Finding the best schedule in this neighborhood is NP-complete in the ordinary sense but can be done in pseudo-polynomial time. We also present experimental results. <s> BIB012 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> This paper addresses the problem of batch scheduling in an unrelated parallel machine environment with sequence dependent setup times and an objective of minimizing the total weighted mean completion time. The jobs' processing times and setup times are stochastic for better depiction of the real world. This is a NP-hard problem and in this paper, new heuristics are developed and compared to existing ones using simulation. The results and analysis obtained from the computational experiments proved the superiority of the proposed algorithm PMWP over the other algorithms presented. <s> BIB013 </s> A survey of scheduling problems with setup times or costs <s> Batch sequence-dependent setup times <s> This paper focuses on minimizing the total completion time in two-machine group scheduling problems with sequence-dependent setups that are typically found in discrete parts manufacturing. As the problem is characterized as strongly NP-hard, three search algorithms based on tabu search are developed for solving industry-size scheduling problems. Four different lower bounding mechanisms are developed to identify a lower bound for all problems attempted, and the largest of the four is aptly used in the evaluation of the percentage deviation of the search algorithms to assess their efficacy. The problem sizes are classified as small, medium and large, and to accommodate the variability that might exist in the sequence-dependent setup times on both machines, three different scenarios are considered. Such finer levels of classification have resulted in the generation of nine different categories of problem instances, thus facilitating the performance of a very detailed statistical experimental design to assess the efficacy and efficiency of the three search algorithms. The search algorithm based on long-term memory with maximal frequencies either recorded a statistically better makespan or one that is indifferent when compared with the other two with all three scenarios and problem sizes. Hence, it is recommended for solving the research problem. Under the three scenarios, the average percentage deviation for all sizes of problem instances solved has been remarkably low. In particular, a mathematical programming based lower bounding mechanism, which focuses on converting (reducing) the original sequence-dependent group scheduling problem with several jobs in each group to a sequence-dependent job scheduling problem, has served well in identifying a high quality lower bound for the original problem, making it possible to evaluate a lower average percentage deviation for the search algorithm. Also, a 16-17-fold reduction in average computation time for solving a large problem instance with the recommended search algorithm compared with identifying just the lower bound of (not solving) the same instance by the mathematical programming based mechanism speaks strongly in favor of the search algorithm for solving industry-size group scheduling problems. Scope and purpose: With an ever increasing demand for setting up manufacturing cells in the production of discrete parts to realize the benefits advocated in lean manufacturing systems, group scheduling has become a topic of research with significant industrial relevance. The problem addressed in this paper is motivated by the need for having to investigate such a problem in the presence of sequence-dependent setups in a two-machine environment to minimize the makespan, which to the best of the authors' knowledge is the first of its kind. Recognizing the complexity of the problem, three search algorithms based on tabu search have been developed to efficiently solve problem instances that belong to nine different categories, as a result of considering three different sizes, ranging from small, medium to large, and three different scenarios. In order to assess the efficacy of the search algorithms, four different lower bounding mechanisms have been developed and the largest of the four is aptly used to evaluate the percentage deviation in every problem instance attempted. The average percentage deviation of the solutions found by the search algorithms has been remarkably low. We view our contribution as that which looks into such detailed levels of investigation, emphasizing a blend of new theory and practice in the area of group scheduling. <s> BIB014
The 1/ST sd,b /C max problem was addressed by  where they modeled the problem as an asymmetric traveling salesman problem with a specific distance matrix. They proposed a polynomial-time algorithm to solve the problem. studied the 1=ST sd;b ; r j = P w j T 2 j problem. They developed a Lagrangian relaxation based approach for the problem, where the setup times are treated as capacity constraints. They compared the performance of this approach with several other procedures, including tabu search and simulated annealing. BIB011 presented a branchand-bound algorithm for the 1=ST sd;b = P C j problem, where they developed a lower bound that is based on a network formulation of the problem. Computational analysis showed that problems with up to 60 jobs and 12 families can be solved optimally using the algorithm. Sourd (2005) addressed the general problem of 1/ST sd,b , SC sd,b with the objective of minimizing the earliness-tardiness and setup costs. He proposed a mixed integer formulation from which lower bounds were derived and used in a branch-andbound algorithm, which can solve problems up to 20 jobs. He also proposed a heuristic to solve large-sized problems. For the same problem, BIB012 showed that finding the optimal solution in the so-called dynasearch neighborhood is NP-hard in the ordinary sense. He also presented a pseudopolynomial algorithm to search the neighborhood. BIB008 considered the 1/ST sd,b problem with the multiple objectives of minimizing the average tardiness and cycle time, and maximizing the machine utilization. They proposed an approach that generates a Pareto optimal solution for the problem. A generalization of the problem R=ST sd;b = P w j T j was studied by BIB003 . In this problem, machines are classified into groups of identical machines. Each job consists of the same number of operations that can be processed simultaneously on different machines. A job is completed when its last operation is finished. Operation processing time depends on the job and the machine group. Job weights are inversely proportional to job due dates. A sequence dependent setup time occurs between batches of operations of different jobs. The authors presented and computationally tested several constructive heuristics: earliest weighted due date and shortest weighted processing time sequencing rules, specific batching heuristic and simulated annealing, using some real problems from semiconductor manufacturing. BIB004 proposed a heuristic algorithm for a modification of the problem P/ ST sd,b /C max , in which a job can be split into several parts allowable to be processed in parallel. A reduction to the traveling salesman problem was used in the heuristic. BIB005 proposed column generation based branch-and-bound algorithms for the P =ST þ sd;b = P w j C j and P =ST sd;b = P w j U j problems. Computational analysis showed that the algorithms are capable of optimally solving problems of medium size, i.e., up to 40 jobs, 4 machines, and 6 families. BIB013 presented several heuristics for the R=ST sd;b = P w j C j problem where both processing and setup times are stochastic. In paper manufacturing, Akkiraju et al. (2001) observed a model generalizing the R/ST sd,b problem with multiple objectives such as P w j T j , P w j E j , and TST. They suggested a heuristic approach based on the so-called Asynchronous Team architecture. Initial solutions are first generated by different experts and computer programs. Then these solutions are perturbed and improved. Finally, a set of Pareto optimal solutions is presented to a decision maker. BIB002 studied a generalization of the R=ST sd;b = P f j problem observed from the Thin Film Transistor Liquid Crystal Display (TFT LCD) assembly process. The objective is a linear combination of the mean flowtime and deviation from product demand. Two specific constructive heuristic algorithms were developed. As in Section 5.3, we will not separately analyze the work in this category under different shop environments. BIB001 developed lower bounds for the Fm/ST sd,b /C max problem under the group technology assumption. They also proposed a heuristic to solve the problem, and empirically evaluated the performance of the proposed heuristic. BIB009 proposed a genetic, a memetic, and a multi-start algorithm for the same problem. They showed that all of the three algorithms outperform the heuristic proposed by BIB001 . They also concluded that the memetic algorithm slightly outperforms the genetic and multi-start algorithms. BIB014 also considered the same problem for the two-machine case, and developed three search algorithms based on tabu search. They developed lower bounds and used these bounds in the evaluation of the developed algorithms. Clearly, the search algorithms of BIB014 and the memetic algorithm of BIB009 remain to be compared.  considered the same model with the criterion of minimizing the total tardiness, and suggested a hybrid genetic algorithm in which a genetic algorithm was used to determine the group sequence, while a heuristic procedure was used to determine the job sequence in each group. BIB006 considered a scheduling problem from a label sticker manufacturing company, and stated that it is equivalent to a generalization of the FF2/ST sd,b /T max problem, where the first stage consists of a single high speed machine and the setup times exist only on the first machine. Since each job has a weight, the objective is to minimize the weighted maximum tardiness. They proposed a heuristic, and showed that it outperforms the current practice in the company. BIB010 studied the problem of scheduling in a tile company. They modeled the problem as FF3/ST sd,b /C max . Their main goal was to identify a set of families with common features. They proposed a heuristic using their defined ''coefficient of similarity'' between the jobs and successfully applied it in the tile company. BIB007 studied the problem F/ ST sd,b , no-wait/C max with family and machine dependent setup and processing times under the batch availability model. Setups are either all anticipatory or all non-anticipatory. Jobs of the same family, though can be partitioned into batches, are required to be processed consecutively on each machine. A setup occurs only between batches of different families. The problem reduces to a generalized traveling salesman problem. A customized heuristic was proposed. A pseudo-polynomial-time algorithm was presented for the single family case. Reddy and Narendran (2003) studied a fivemachine permutation flow shop problem with dynamically arriving jobs belonging to different families in a stochastic environment where both the processing times and the time between arrivals are assumed to be exponential random variables. Sequence dependent setup times occur between the jobs of distinct families. Reddy and Narendran compared the quality of nine heuristics (a combination of three dispatching rules and three queue selection rules) with regard to simulated data. Their objective was to minimize (i) the average job time in the system, (ii) the average job tardiness, and (iii) the percentage of tardy jobs.