A survey of scheduling problems with setup times or costs <s> Introduction <s> We propose a three-phase heuristic for the problem of minimizing the total weighted tardiness on a single machine in the presence of sequence-dependent setup times. In the first phase a number of parameters characterizing the problem instance at hand are calculated. In the second phase we develop a schedule by using a new priority rule whose parameters are calculated based on the results of the first phase. Computational experiments show that this rule significantly outperforms the only other rule so far developed in the literature. The third phase consists of a local improvement procedure to improve the schedule obtained in the second phase. The procedure we suggest has been successfully implemented in an industrial scheduling system. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Introduction <s> This contribution summarizes recent work in the field of lot sizing and scheduling. The objective is not to give a comprehensive literature survey, but to explain differences of formal models and to provide some first readings recommendations. Our focus is on capacitated, dynamic, and deterministic cases. To underscore the importance of the research efforts, current practice is described and its shortcomings are exposed. Mathematical programming models where the planning horizon is subdivided into several discrete periods are given for both approaches that are well-established and approaches which may represent tomorrow's state of the art. Two research directions are discussed in more detail: continuous time models and multi-level lot sizing and scheduling. The paper concludes with some advice for future research activities. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Introduction <s> We review the static scheduling research in which the setup time or cost is of main concern in the problem studied. The literature is classified into job, class and job-andclass setup situations. Also, each situation is further classifed on the basis of sequence dependence and separability of setup. Directions for future research on setup time problems are also identified. <s> BIB003 </s> A survey of scheduling problems with setup times or costs <s> Introduction <s> There is an extensive literature on models that integrate scheduling with batching decisions. Jobs may be batched if they share the same setup on a machine. Another reason for batching occurs when a machine can process several jobs simultaneously. This paper reviews the literature on scheduling with batching, giving details of the basic algorithms, and referencing other significant results. Special attention is given to the design of efficient dynamic programming algorithms for solving these types of problems. <s> BIB004 </s> A survey of scheduling problems with setup times or costs <s> Introduction <s> Abstract In this paper, we investigate the problem of scheduling jobs on identical parallel machines. The jobs are assumed to have sequence dependent setup times independent of the machine. Each job has a processing time, a due date, and a weight for penalizing tardiness. The objective of scheduling is to find a sequence of the jobs which minimizes the sum of weighted tardiness. We propose an extension of the ATCS (Apparent Tardiness Cost with Setups) rule developed by Lee et al. (1997) which utilizes some look-ahead parameters for calculation the priority index of each job. Scheduling jobs on parallel machines with sequence-dependent set-up times. Technical report. Columbia University; Lee, Y.H., Bhaskaran, K., & Pinedo, M., 1997. A heuristic to minimize the total weighted tardiness with seqence-dependent setups. IIE Transactions, 29, 45–52.) which utilizes some look-ahead parameters for calculating the priority index of each job. The look-ahead parameters were introduced as a tuning mechanism which adjusts the discount rate inside the priority calculation according to the given problem characteristics. To determine the proper values of the look-ahead parameters, Lee identified some measures for describing problem characteristics. They proposed four factors to describe properties of the problem instances, and a heuristic curve-fitting method was used to determine the equations for calculating proper values of the look-ahead parameters. In our approach, an additional factor for measuring the problem characteristics is introduced and we also utilize a neural network to get more accurate values of the look-ahead parameters. Our computational results show that the proposed approach outperforms Lee et al.’s (1997) original ATCS and a simple application of ATCS. <s> BIB005 </s> A survey of scheduling problems with setup times or costs <s> Introduction <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> BIB006 </s> A survey of scheduling problems with setup times or costs <s> Introduction <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> BIB007 </s> A survey of scheduling problems with setup times or costs <s> Introduction <s> This paper considers a complex scheduling problem in the chemical process industry involving batch production. The application described comprises a network of production plants with interdependent production schedules, multi-stage production at multi-purpose facilities, and chain production. The paper addresses three distinct aspects: (i) a scheduling solution obtained from a genetic algorithm based optimizer, (ii) a mechanism for collaborative planning among the involved plants, and (iii) a tool for manual updates and schedule changes. The tailor made optimization algorithm simultaneously considers alternative production paths and facility selection as well as product and resource specific parameters such as batch sizes, and setup and cleanup times. The collaborative planning concept allows all the plants to work simultaneously as partners in a supply chain resulting in higher transparency, greater flexibility, and reduced response time as a whole. The user interface supports monitoring production schedules graphically and provides custom-built utilities for manual changes to the production schedule, investigation of various what-if scenarios, and marketing queries. <s> BIB008 </s> A survey of scheduling problems with setup times or costs <s> Introduction <s> This paper presents a scheduling problem for unrelated parallel machines with sequence-dependent setup times, using simulated annealing (SA). The problem accounts for allotting work parts of L jobs into M parallel unrelated machines, where a job refers to a lot composed of N items. Some jobs may have different items while every item within each job has an identical processing time with a common due date. Each machine has its own processing times according to the characteristics of the machine as well as job types. Setup times are machine independent but job sequence dependent. SA, a meta-heuristic, is employed in this study to determine a scheduling policy so as to minimize total tardiness. The suggested SA method utilizes six job or item rearranging techniques to generate neighborhood solutions. The experimental analysis shows that the proposed SA method significantly outperforms a neighborhood search method in terms of total tardiness. <s> BIB009 </s> A survey of scheduling problems with setup times or costs <s> Introduction <s> Lot sizing is one of the most important and also one of the most difficult problems in production planning. This subject has been studied extensively in the literature. In this article, we consider single-level lot sizing problems, their variants and solution approaches. After introducing factors affecting formulation and the complexity of production planning problems, and introducing different variants of lot sizing and scheduling problems, we discuss single-level lot sizing problems, together with exact and heuristic approaches for their solution. We conclude with some suggestions for future research. <s> BIB010 </s> A survey of scheduling problems with setup times or costs <s> Introduction <s> Lot streaming—the process of splitting a production lot into sublots—has been a common practice in flow-shop systems during the past decade. Nevertheless, a major limiting assumption has been made in the analysis of these systems in that the setup time is, at most, lot-attached but not sublot-attached. In this paper, we consider the single and multiple batch flow-shop lot-streaming problems with sublot-attached setup times. A fast, optimal solution algorithm for the single batch problem is presented. For the multiple batch problem, we propose a near optimal solution procedure which is optimal in two-machine flow-shops. Computational results are also presented for the multiple batch problem which indicate both the efficiency and effectiveness of this procedure. <s> BIB011 </s> A survey of scheduling problems with setup times or costs <s> Introduction <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> Introduction <s> A model for scheduling grouped jobs on identical parallel machines is addressed in this paper. The model assumes that a set-up time is incurred when a machine changes from processing one type of component to a different type of component, and the objective is to minimize the total earliness-tardiness penalties. In this paper, the algorithm of soft computing, which is a fuzzy logic embedded Genetic Algorithm is developed to solve the problem. The efficiency of this approach is tested on several groups of random problems and shows that the soft computing algorithm has potential for practical applications in larger scale production systems. <s> BIB013 </s> A survey of scheduling problems with setup times or costs <s> Introduction <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> BIB014 </s> A survey of scheduling problems with setup times or costs <s> Introduction <s> Lot streaming is a technique used to split a processing batch into several transfer batches. In this way, overlapping operations can be performed in different manufacturing stages, and production can be accelerated. This paper proposes two cost models for solving lot streaming problems in a multistage flow shop. The purpose is to determine the optimal processing batch size and the optimal number of transfer batches that minimize the total annual cost in each model. In the first model, a more complete and accurate method is developed to compute the costs of raw materials, work-in-process, and finished-product inventories. The total cost includes the setup cost, the transfer batch movement cost, the three-type inventory holding cost, and the finished-product shipment cost. The second model contains not only the four costs in the first model, but also the imputed cost associated with the makespan time. The total annual cost functions in both models are shown to be convex, and two solution approaches are suggested. An experiment consisting of three phases was conducted to explore the effect on the optimal solution when changing the value of one parameter at a time. The results indicate that three parameters have significant effects on the optimal solution. <s> BIB015 </s> A survey of scheduling problems with setup times or costs <s> Introduction <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> BIB016 </s> A survey of scheduling problems with setup times or costs <s> Introduction <s> Flowshop scheduling problems with setup times arise naturally in many practical situations. This paper provides a review of static and deterministic flowshop scheduling research involving machine setup times. The literature is classified into four broad categories, namely sequence independent job setup times, sequence dependent job setup times, sequence independent family setup times, and sequence dependent family setup times. Using the suggested classification scheme, this paper organizes the flowshop scheduling literature involving setup and/or removal times and summarizes the existing research for different flowshop problem types. This review reveals that, while a considerable body of literature on this subject has been created, there still exist several potential areas worthy of further research. <s> BIB017
The first systematic approach to scheduling problems was undertaken in the mid-1950s. Since then, thousands of papers on different scheduling problems have appeared in the literature. The majority of these papers assumed that the setup time (cost) is negligible or part of the job processing time (cost). While this assumption simplifies the analysis and/or reflects certain applications, it adversely affects the solution quality of many applications of scheduling that require an explicit treatment of setup times (costs). The interest in scheduling problems that treat setup times (costs) as separate began in the mid-1960s. The corresponding results have been 0377-2217/$ -see front matter Ó 2006 Elsevier B.V. All rights reserved. doi: 10.1016/j.ejor.2006.06.060 summarized in the survey papers of Allahverdi et al. (1999) , BIB003 , BIB017 and BIB004 . BIB003 concentrated on static and deterministic scheduling problems. BIB017 reviewed flow shop scheduling problems, while BIB004 surveyed scheduling problems with batching. Allahverdi et al. (1999) provided a comprehensive review of the literature including dynamic and stochastic problem settings in different shop environments; single-machine, parallel machines, flow shops, and job shops. There has been a significant increase in interest in scheduling problems involving setup times (costs) since the publication of the above surveys whereby an average of more than 40 papers per year have been added to the literature. This increase stems from the fact that there are tremendous savings when setup times/costs are explicitly incorporated in scheduling decisions in various real world industrial/service environments. Allahverdi and Soroush (in press ) present a classification of various applications and the benefits of scheduling involving separate setup times/costs. The objective of the current survey paper is to review the literature on separate setup times (costs) involving static, dynamic, deterministic, and stochastic problems for all shop environments, including single-machine, parallel machines, flow shops (regular flow shop, no-wait flow shop, flexible flow shop, assembly flow shop), job shops, open shops, and others. The current paper is a continuation of the earlier survey papers of Allahverdi et al. (1999) and BIB004 covering more than 300 papers that were published in 1999-2006. We do not cite in this survey paper the earlier research that was covered by Allahverdi et al. (1999) and BIB004 even when a comparison of a new result with a result that was referenced in these two papers is required. Therefore, rather than stating that, e.g., BIB005 proposed the use of a neural network to get values for parameters in calculating a priority rule for the P =ST sd = P w i T i problem, where their computational results indicated that their proposed approach outperforms that of BIB001 , we state that Park et al.'s computational results indicated that their proposed approach outperforms that of an earlier approach. This is because BIB001 had already been cited in Allahverdi et al. (1999) and the already long reference list of the current paper. We do not review setup time or setup cost research for lot-sizing and scheduling problems in the context of inventory management, see the surveys of BIB002 and BIB010 , for vehicle routing and scheduling problems, see the review of  , for lot streaming problems with continuous batch sizes, e.g., BIB015 and BIB011 , and research on complex industrial problems involving time indexed variables and continuous batch sizes, e.g., BIB008 . The importance and applications of scheduling models with explicit considerations of setup times (costs) have been discussed in several studies since the mid-1960s. Following are some recent applications: • Laguna (1999) considered a facility that produces supplies to photocopiers and laser printers. He pointed out that changing production from one toner to another results in large setup times (generally of the order of days). BIB006 addressed the problem of manufacturing printed circuit boards on an automated insertion machine. They stated that the problem is a setup time scheduling problem. • In the textile industry, setup times are significant and have to be considered as separate as mentioned by BIB007 . Fabric types are assigned to looms equipped with wrap chains. When the fabric type is changed on a machine, the wrap chain must be replaced and the time it takes depends on the current and the previous fabric types.  presented a case study of batching in mass service operations in the example of a court. The interviewed judges noted that setup times and costs are due to trips to court, pre-court meetings, mental preparation, and communication of instructions. • Many WWW applications require access, transfer, and synchronization of large multimedia data objects (MDOs), such as audio, video, and images, across a communication network. The processing and transfer of large MDOs across the Web affects the response time to end users. Therefore, the MDO scheduling process is a critical aspect of distributed multimedia database systems and it is very important to provide distributed systems with an efficient multimedia data scheduling strategy. Allahverdi and Al-Anzi (2002) showed that the MDO scheduling prob-lem for WWW applications can be modeled as a two-machine flow shop scheduling problem with separate setup times. • BIB009 considered the production of compound semiconductors that are used for electronic components in information displays, mobile telecommunications, and wireless data communications. They pointed out that the machines used in the production of compound semiconductors should be adjusted whenever different types of wafers are diced. Therefore, different setup times are required depending on wafer sequences. BIB012 described a biaxially oriented polypropylene (BOPP) film factory, which produces products such as adhesive tapes, photo albums, foodstuff packages, book covers, etc. They stated that the time, raw materials, and equipment necessary to prepare for the next job in the factory depend on the preceding job, and therefore, the setup times and setup costs are sequence-dependent. • BIB013 considered stamping plants that are used by most auto-makers. In such plants, the setup time between manufacturing parts involves the changing of heavy dies, which indicates the significance of setup times. • BIB014 described a label sticker manufacturing company. They stated that the problem is a two-stage hybrid flow shop where the first stage is a single high speed machine that is used to glue the surface material and liner together to produce the label stickers. They stated that when the machine in the first stage is changed over from jobs in one class to jobs in another class, a sequence-dependent setup time is required for the changeover task. • BIB016 addressed the problem of product grouping in the tile industry and stated that the problem can be modeled as a three-stage hybrid flow shop with separate and sequencedependent setup times. They pointed out that the objective for such a problem is to minimize the changeover (setup) time in order to reduce the production time.