A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> In today's fast-paced Just-In-Time and mass customization manufacturing in a sequence-dependent setup environment, the challenge of making production schedules to meet due-date requirements is becoming a more complex problem. Unfortunately, much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper considers the problem of minimizing tardiness, a common measure of due-date performance, in a sequence-dependent setup environment. Simulated annealing was used to solve the sequencing problem, and its performance was compared with random search. Our experimental results show that the algorithm can find a good solution fairly quickly, and thus can rework schedules frequently to react to variations in the schedule. The algorithm is invaluable for 'on-line' production scheduling and 'last-minute' changes to production schedule. The results of this research also suggest ways in which more complex and realistic job shop environments, such as multiple machines with a higher number of jobs in the sequence, and other scheduling objectives can be modeled. This research also investigates computational aspects of simulated annealing in solving complex scheduling problems. <s> BIB001 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Abstract In a work center where multiple products have to be processed, setups may absorb a large part of the total time that is available for production of items and execution of setups. The fraction of time that the machine is busy (the total utilization) is the sum of the fraction of time spent on actual production (the productive utilization) and the fraction of time spent on setups (the setup utilization). By processing the items in batches one can save setups. When capacity is fixed, the setup utilization is fully determined by the batching decision. In practice, examples can be found where the setup utilization is used as a guide for making decisions on batch sizes. In those cases management sets a maximum on the fraction of time spent on executing setups. In this paper we will substantiate this procedure by studying a queueing delay batching model. When optimal batch sizes are used in the work center, the implied setup utilization is less than 0.175. As a consequence, whenever the setup utilization is higher than 17.5% the batch sizes can be improved in order to obtain shorter expected waiting times in the queue. <s> BIB002 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We consider a scheduling problem in which n jobs are grouped into F groups and are to be processed on a single machine. A machine setup time is required when the machine switches from one group of jobs to the other. All jobs have a common due date that needs to be determined. The objective is to find an optimal common due date and an optimal sequence of jobs to minimize the sum of the cost of tardy jobs and the cost related to the common due date. We consider two cases: 1.(i) the jobs have to be processed in groups; and 2.(ii) the jobs do not have to be processed in groups. Analytical results are presented and computational algorithms are developed. <s> BIB003 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Abstract We review the current state of scheduling theory concerning the processing of several families of jobs on single or parallel facilities, where a setup time may be incurred whenever there is a switch from processing a job in one family to a job in another family. We also consider cases with the group technology assumption that the jobs must be scheduled contiguously. Using available results from the literature, we classify the different problems as NP-hard, efficiently solvable or open. We refine some old results and present several new ones. In particular, we show that under the group technology assumption, even with sequence-independent setup times, minimizing the number of late jobs on a single machine is NP-hard. We investigate the complexity of single machine scheduling with interfamily setup times, when we seek to minimize the maximal cost, where the cost for each job is a nondecreasing function of its completion time. We also prove that, when scheduling on parallel machines under the group technology assumption with sequence-independent setup times, minimizing total completion times is NP-hard unless all families contain the same number of jobs. <s> BIB004 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> This paper considers a single machine group scheduling problem. All jobs are classified into groups and the jobs within a group are processed contiguously on the machine. A sequence-independent setup time is incurred between each two consecutively scheduled groups. This paper presents a solution procedure which utilizes Smith's algorithm and a proposed modified Smith's algorithm to find an optimal job sequence and an optimal group sequence which minimizes the mean flow time of jobs subject to the constraint that no jobs are tardy. The complexity of the algorithm is shown to have a polynomial running time in the number of groups and jobs. <s> BIB005 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We propose and investigate a genetic algorithm for scheduling jobs about an unrestricted common due date on a single machine. The objective is to minimize total earliness and tardiness cost where early and tardy penalty rates are allowed to be arbitrary for each job. Jobs are classified into families and a family setup time is required between jobs from two different families. Results from a computational study are promising with close to optimal solutions obtained rather easily and quickly. <s> BIB006 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We investigate the single-machine sequencing problem in which each job has a processing time and a delivery time. The jobs are divided into families and a set-up time is incurred whenever there is a switch from a job in one family to a job in another family. This set-up only depends on the family of the job next to come and hence is sequence independent. The objective to to find a sequence of jobs that minimizes the time by which all jobs are delivered. The best polynomial-time approximation algorithm that was previously known for this problem is due to Zdrzalka and has a worst-case guarantee of 3 2. In this paper, we demonstrate the existence of a polynomial time approximation scheme for the problem. © 1998 John Wiley & Sons, Ltd. <s> BIB007 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> A single facility scheduling problem concerned with the production of jobs in a set of customer orders is analysed. Each order consists of several jobs. Based on the concept of group technology, jobs can be grouped into different classes. Jobs in the same class can be processed together in a combined batch, where batches of different classes are initiated with a setup time. Furthermore, the order availability is assumed, which means the finished jobs of an order cannot be shipped out to its customer until all other jobs in the same order have been completed. Under the above production environment, a branch-and-bound algorithm is developed to determine a schedule with the minimum mean flow time of orders. A heuristic is also developed to solve large-sized problems. Computational results of both approaches are reported. <s> BIB008 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> This paper addresses a single machine sequencing problem with variable processing times and sequence-dependent setups. The objective is to find the best trade-off between the JIT goal and the processing time compression and extension costs by simultaneously determining the job sequence and processing times for concerned jobs. Due to the combinatorial nature of the problem, it cannot be optimally solved in polynomial time. A tabu search approach is used to provide good and quick solutions. To improve the computational efficiency, an adaptive neighbourhood generation method is proposed and used in the tabu search algorithm. A total of 100 problems of different sizes have been solved to test the proposed approach. Our computational experience shows that the adaptive approach outperforms several other neighbourhood generation methods in terms of both convergence rate and solution quality. The effects of the search parameters are also discussed. <s> BIB009 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> A hybrid genetic algorithm (HGA) is proposed for the single machine, single stage, scheduling problem in a sequence dependent setup time environment within a fixed planning horizon (SSSDP). It incorporates the elitist ranking method, genetic operators, and a hill-climbing technique in each searching area. To improve the performance and efficiency, hill climbing is performed by uniting the Wagner-Whitin Algorithm with the problem-specific knowledge. The objective of the HGA is to minimize the sum of setup cost, inventory cost, and backlog cost. The HGA is able to obtain a superior solution, if it is not optimal, in a reasonable time. The computational results of this algorithm on real life SSSDP problems are promising. In our test cases, the HGA performed up to 50% better than the Just-In-Time heuristics and 30% better than the complete batching heuristics. <s> BIB010 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> This paper considers a single machine scheduling problem with ready and due times constraints on jobs, shutdown constraints on the machine and sequence dependent set-up times among jobs. The shutdown is a disruptive event such as holiday, breaks or machine maintenance, and has a prespecified period when the machine will be interrupted. If no pre-emption is allowed for jobs, shutdown constraints divide the planning horizon into disconnected time windows. An optimization algorithm based on the branch-and-bound method is developed to minimize the maximum tardiness for solving the problem. This paper further develops the post-processing algorithm that manipulates the starting time of the shutdown period so as to reduce the obtained maximum tardiness. The post-processing algorithm can determine plural schedules to reduce the maximum tardiness, and the production manager will select the objective schedule among them for the interest of overall efficiency. Computational results for the proposed algorithms will i... <s> BIB011 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> The majority of scheduling literature assumes that the machines are available at all times. In this paper, we study single machine scheduling problems where the machine maintenance must be performed within certain intervals and hence the machine is not available during the maintenance periods. We also assume that if a job is not processed to completion before the machine is stopped for maintenance, an additional setup is necessary when the processing is resumed. Our purpose is to schedule the maintenance and jobs to minimize some performance measures. The objective functions that we consider are minimizing the total weighted job completion times and minimizing the maximum lateness. In both cases, maintenance must be performed within a fixed period T, and the time for the maintenance is a decision variable. In this paper, we study two scenarios concerning the planning horizon. First, we show that, when the planning horizon is long in relation to T, the problem with either objective function is NP-complete, and we present pseudopolynomial time dynamic programming algorithms for both objective functions. In the second scenario, the planning horizon is short in relation to T. However, part of the period T may have elapsed before we schedule any jobs in this planning horizon, and the remaining time before the maintenance is shorter than the current planning horizon. Hence we must schedule one maintenance in this planning horizon. We show that the problem of minimizing the total weighted completion times in this scenario is NP-complete, while the shortest processing time (SPT) rule and the earliest due date (EDD) rule are optimal for the total completion time problem and the maximum lateness problem respectively. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 845–863, 1999 <s> BIB012 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> This paper examines heuristic solution procedures for scheduling jobs on a single machine to minimize the maximum lateness in the presence of setup times between different job families. It reviews the state of knowledge about the solution of this problem, which is known to be difficult to solve in general, and examines natural solution approaches derived from some of the underlying theory. The emphasis is on the design and computational evaluation of new heuristic procedures. c 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 978{991, 1999 <s> BIB013 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We consider the problem of allocating a single server to families of jobs with random service times and due dates. Furthermore, a set-up is required when the server switches from one job family to another. We address the problems of minimizing expected weighted flow time, expected maximum lateness, and total weighted tardiness with emphasis on problems for which it is assumed that each family can be set up only once (the Group Technology assumption). We derive conditions under which simple sequencing rules are optimal for each of these problems with group technology. <s> BIB014 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Abstract. We study the problems of scheduling jobs, with different release dates and equal processing times, on two types of batching machines. All jobs of the same batch start and are completed simultaneously. On a serial batching machine, the length of a batch equals the sum of the processing times of its jobs and, when a new batch starts, a constant setup time s occurs. On a parallel batching machine, there are at most b jobs per batch and the length of a batch is the largest processing time of its jobs. We show that in both environments, for a large class of so called “ordered” objective functions, the problems are polynomially solvable by dynamic programming. This allows us to derive that the problems where the objective is to minimize the weighted number of late jobs, or the weighted flow time, or the total tardiness, or the maximal tardiness are polynomial. In other words, we show that 1|p-batch,b<n, ri, pi=p|F and 1|s-batch, ri, pi=p|F, are polynomial for F∈{∑wiUi,∑wiCi,∑Ti, Tmax}. The complexity status of these problems was unknown before. <s> BIB015 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <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> BIB016 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We study the problem of scheduling jobs on a serial batching machine ::: to minimize total tardiness. Jobs of the same batch start and are ::: completed simultaneously and the length of a batch equals the sum of ::: the processing times of its jobs. When a new batch starts, a constant ::: setup time s occurs. This problem 1| s-batch | ∑ T i is ::: known to be NP-Hard in the ordinary sense. In this paper we show that ::: it is solvable in pseudopolynomial time by dynamic programming. <s> BIB017 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> The scheduling problem considered consists of determining a feasible schedule when each job is defined with a ready date, a processing time different on each machine and a deadline. They are setup time sequence dependent. The parallel machines are composed of 2 types. The first one is characterized with "cheap" machines, and the second one with "expensive" machines. The objective function is to first find a feasible schedule and then to minimize the cost due to assignment and setup time costs. The method presented in this paper is based on a three-phase heuristic. The first phase is based on an iterative heuristic, the second one on a genetic algorithm and the third one on a branch and bound for post optimization. <s> BIB018 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We consider the problem of scheduling N jobs on M parallel machines that operate at different speeds (known as uniform parallel machines), to minimize the sum of earliness and tardiness costs. Jobs are assumed to arrive in a dynamic albeit deterministic manner, and have nonidentical due dates. Violations of due dates result in earliness or tardiness penalties that may be different for different jobs. Setup times are job-sequence dependent and may be different on different machines based on the characteristics of the machines. For this problem, we present a mixed integer formulation that has substantially fewer zero–one variables than typical formulations for scheduling problems of this type. We present our computational experience in using this model to solve small sized problems, and discuss solution approaches for solving larger problems. ::: ::: ::: Scope and purpose ::: ::: In JIT environments, firms face the need to complete jobs as close to their due dates as possible. Failure to do so would result in earliness and/or tardiness costs and the optimum schedule would seek to minimize functions of these costs. In many real-world situations, the problem is greatly complicated by the presence of disparate issues such as: (i) uniform parallel machines that are capable of processing these jobs at different speeds; (ii) sequence-dependent setup times; (iii) distinct job due dates; (iv) distinct job ready dates; and (v) distinct earliness and/or tardiness costs for each job. For this complex problem, we present a compact mathematical model and describe our computational experience in using this model to solve small sized problems. <s> BIB019 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> This paper presents a genetic algorithm for a single machine-scheduling problem with the objective of minimizing total tardiness. Each job has its own due date and the set-up times are sequence dependent. The parameters of the genetic algorithm are determined by a statistical method. For small problems, the solutions given by the proposed method are compared with solutions provided by a commercial package, and for larger problems, with those obtained by a heuristic proposed in the literature. <s> BIB020 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Much of the research on operations scheduling problems has either ignored setup times or assumed that setup times on each machine are independent of the job sequence. This paper considers the problem of scheduling a single machine for minimizing total tardiness in a sequence dependent setup environment. The comparative performance of branch-and-bound, genetic search, simulated annealing and random-start pairwise interchange was evaluated in this problem setting. The experimental results suggest that simulated annealing and random-start pairwise interchange are viable solution techniques that can yield good solutions to a large combinatorial problem when considering the tardiness objective with sequence dependent setup times. However, branch-and-bound may be the preferred solution technique in solving smaller problems, and it is the only solution technique tested that will confirm an optimum solution has been reached. The methods considered in this research offer promise to deal with a class of scheduling problems, which have been considered difficult by both researchers and practitioners. <s> BIB021 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Abstract This paper examines an optimal solution procedure for scheduling jobs on a single machine to minimize the maximum lateness in the presence of setup times between different job families. We exploit special structure to compress the effective problem size by creating composite jobs; then we accelerate the enumeration with dominance properties and lower bounds. Our computational evaluation highlights the size of setup times and the variation in due dates. <s> BIB022 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> SUMMARY A recent trend in the analysis of scheduling models integrates batching decisions with sequencing decisions. The interplay between batching and sequencing reects the realities of the small-volume, high-variety manufacturing environment and adds a new feature to traditional scheduling problems. Practical interest in this topic has given rise to new research eorts, and there has been a series of articles in the research literature surveying the rapidly developing state of knowledge. Exam- ples include Ghosh (1), Liaee and Emmons (2), Potts and Van Wassenhove (3), and Webster and Baker (4). This paper deals with an important theoretical and practical problem in this area. We examine the single-machine model with family (or group) set-up times and a criterion of minimizing total weighted job completion time (weighted owtime). We propose new lower bounds for this problem, and then turn our attention to renement of a previously proposed branch-and-bound algorithm. The benets of our renements are illustrated by computational experiments. <s> BIB023 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Abstract In this paper, we examine the scheduling of jobs, each of which comprises a standard and a specific component, on a single machine. A set-up time is required before each batch of standard components is processed. A job is completed when both its standard and specific components have been processed and are available. Standard components only become available when the batch to which they belong is completed, whereas specific components are available on completion of their processing. We present results for two well-known due-date related criteria. In particular, an O( n 2 ) dynamic programming algorithm is derived for the problem of minimising the maximum lateness. For minimising the number of late jobs, we show that the problem is NP-hard and give a dynamic programming algorithm that requires pseudo-polynomial time. Finally, we show that a variant of the number of late jobs problem, in which there is a common processing time for the standard components, is solvable in O (n 4 log n) time. <s> BIB024 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Scheduling problems with earliness and tardiness penalties are commonly encountered in today's manufacturing environment due to the current emphasis on the just-in-time (JIT) production philosophy. The problem studied in this work is the parallel machine earliness-tardiness non-common due date sequence-dependent set-up time scheduling problem (PETNDDSP) for jobs with varying processing times, where the objective is to minimize the sum of the absolute deviations of job completion times from their corresponding due dates. The research presented provides a first step towards obtaining near optimal solutions for this problem using local search heuristics in the framework of a meta-heuristic technique known as simulated annealing (SA). The computational study shows that, using the SA methodology, significant improvements to the local search heuristic solutions can be achieved for problems of this type. <s> BIB025 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent 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> BIB026 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <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> BIB027 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent 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> BIB028 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Abstract In this paper, a new memetic algorithm (MA) for the total tardiness single machine scheduling (SMS) problem with due dates and sequence-dependent setup times is proposed. The main contributions with respect to the implementation of the hybrid population approach are a hierarchically structured population conceived as a ternary tree and the evaluation of three recombination operators. Concerning the local improvement procedure, several neighborhood reduction schemes are developed and proved to be effective when compared to the complete neighborhood. Results of computational experiments are reported for a set of randomly generated test problems. The memetic approach and a pure genetic algorithm (GA) version are compared with a multiple start algorithm that employs the all-pairs neighborhood as well as two constructive heuristics. <s> BIB029 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> The single-machine family scheduling problem of minimizing the number of late jobs has been known to be NP-hard, but whether it is NP-hard in the strong sense is cited as an open problem in several reviews. In this note, we prove that this problem is strongly NP-hard even if all set-up times and processing times are one unit. Copyright © 2001 John Wiley & Sons, Ltd. <s> BIB030 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> The single-machine sequence-independent class setup scheduling problem is examined in this paper. It is assumed that jobs are classified into classes and a setup is required between jobs of different classes, but not of the same class. Furthermore, this setup time is fixed and depends only on the current job. Since the problem is NP-hard, a heuristic algorithm is proposed to find an approximate schedule that minimizes the maximum lateness on a set of jobs. The algorithm can easily be modified to solve the maximum tardiness problems as well. The accuracy of the heuristic algorithm in generating near optimal solutions is empirically evaluated. Scope and purposeFor batch manufacturing, it maybe desirable to produce many items of the same type, or class, at the same run in order to save the setup cost. However, committing facilities to long production runs for one product may inevitably make others tardy. Small batch size may conform urgent jobs to their delivery date, but one of the consequences would be the loss of productive efficiency due to numerous setups. Therefore, scheduling is basically a trade-off between the inherently conflicting efficiency measure and due-date compliance. This paper considers a single-machine scheduling problem in which jobs are classified into classes and a setup is required between jobs of different classes. The setup time is fixed and depends only on the current job. This problem is called a sequence-independent class setup problem and is NP-complete. <s> BIB031 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Abstract Jobs are processed by a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time common for all batches. Both the job processing times and the setup time can be compressed through allocation of a continuously divisible resource. Each job uses the same amount of the resource. Each setup also uses the same amount of the resource, which may be different from that for the jobs. Polynomial time algorithms are presented to find an optimal batch sequence and resource values such that either the total weighted resource consumption is minimized, subject to meeting job deadlines, or the maximum job lateness is minimized, subject to an upper bound on the total weighted resource consumption. The algorithms are based on linear programming formulations of the corresponding problems. <s> BIB032 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> The problem of scheduling n jobs on a single machine in batches to minimize some regular cost functions is studied. Jobs within each batch are processed sequentially so that the processing time of a batch is equal to the sum of the processing times of the jobs contained in it. Jobs in the same batch are completed at the same time when the last job of the batch has finished its processing. A constant set-up time precedes the processing of each batch. The number of jobs in each batch is bounded by some value b. If b < n, then the problem is called bounded. Otherwise, it is unbounded. For both the bounded and unbounded problems, dynamic programming algorithms are presented for minimizing the maximum lateness, the number of late jobs, the total tardiness, the total weighted completion time, and the total weighted tardiness when all due dates are equal, which are polynomial if there is a fixed number of distinct due dates or processing times. More efficient algorithms are derived for some special cases of both... <s> BIB033 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent 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> BIB034 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent 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> BIB035 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent 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> BIB036 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We compare several heuristics for solving a single machine scheduling problem. In the operating situation modelled, setup times are sequence-dependent and the objective is to minimize total tardiness. We describe an Ant Colony Optimization (ACO) algorithm having a new feature using look-ahead information in the transition rule. This feature shows an improvement in performance. A comparison with a genetic algorithm, a simulated annealing approach, a local search method and a branch-and-bound algorithm indicates that the ACO that we describe is competitive and has a certain advantage for larger problems. <s> BIB037 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We consider in this paper the single-machine preemptive scheduling problem with job release dates, delivery times and preemption penalties, where each time a job is started, whether initially or after preemption, a job-dependent setup must take place. First, we prove that the problem is strongly NP-hard. Then, we present a dynamic programming algorithm and a polynomial time approximation scheme. <s> BIB038 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> In this paper, we present a tabu search algorithm that schedules N jobs to a single machine in order to minimise the maximum lateness of the jobs. The release times, due dates, and sequence-dependent set-up times of the jobs are assumed to exist. We modified the original tabu search method to be suitable for the scheduling problem. The proposed tabu search algorithm is composed of two parts: a MATCS (modified apparent tardiness cost with set-ups) rule for finding an efficient initial solution, and the tabu search method to seek a near optimal solution from the initial solution. The experimental results show that the tabu search algorithm obtains much better solutions more quickly than the RHP (rolling horizon procedure) heuristic suggested by Ovacik and Uzsoy. <s> BIB039 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> In view of the properties of multi-product batch scheduling problem with major and minor setup times that a practical steel pipe plant of iron and steel industry usually has, a 0-1 mixed integer-programming model to the problem is developed with minimizing the job maximum lateness (L/sub max/) as the optimal objective function. A tabu search-based heuristic (TSH) algorithm is proposed by analyzing the optimal properties of the problem. The simulation results have confirmed its feasibility and effectiveness. <s> BIB040 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We study the problem of nonpreemptively scheduling n jobs on m identical machines in parallel to maximize the weighted number of jobs that are completed exactly at their due dates. We show that this problem is solvable in polynomial time even if positive set-up times are allowed. Moreover, we show that if due date tolerances are permitted, then already the single-machine case is NP-hard even if all set-up times are zero and all weights are the same. <s> BIB041 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> The problems of scheduling groups of jobs under the group technology assumption are studied. The two remaining open questions posed in the literature a decade ago about the computational complexity of these problems (J. Oper. Res. Soc., 1992; 43:395–406), are answered. The parallel machine problem to minimize the total job completion time is proved to be NP-hard in the strong sense, even if group set-up times are equal to zero. A dynamic programming algorithm is presented to solve this problem, which is polynomial if the number of machines is fixed. The two-machine open-shop problem to minimize the makespan is proved to be NP-hard in the ordinary sense, even if there are zero group set-up times and equal job processing times on both machines. It is shown that the latter problem under the condition that any group can be split into batches does not reduce to the problem where the splittings are not allowed, i.e. the group technology assumption is satisfied. Copyright © 2002 John Wiley & Sons, Ltd. <s> BIB042 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> In this paper, we consider the single machine batching problem with family setup times to minimize maximum lateness. While the problem was proved to be binary NP-hard in 1978, whether the problem is strongly NP-hard is a long-standing open question. We show that this problem is strongly NP-hard. <s> BIB043 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We examine the problem of scheduling jobs, on a single processor to minimise the total earliness and tardiness costs about a common due date. Jobs belong to mutually exclusive families and a sequence independent setup task is required when processing switches from a job of one family to a job of another.We extend earlier results to obtain necessary optimal conditions for this problem. These are then used to generate a fast heuristic. Its performance is compared with a lowerbound, a greedy heuristic, a genetic algorithm and for small problems, the optimal solution. <s> BIB044 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviation of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then O(n3 log n) and O(n5) time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems. <s> BIB045 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> The effective management of shop floor resources is an important factor in achieving the goals of a manufacturing company. The need for effective scheduling is particularly strong in complex manufacturing environments. This paper presents an efficient due date density-based categorising heuristic to minimise the total weighted tardiness (TWT) of a set of tasks with known processing times, due dates, weights and sequence-dependent setup times for parallel machines scheduling. The proposed heuristic is composed of four phases. In the first phase, jobs are listed by the earliest due date (EDD). The second phase computes the due date gaps between listed jobs and categorises the jobs based on the due date density. In the third phase, the sequence of jobs is improved by a tabu search (TS) method. The fourth phase allocates each job to machines. The comprehensive simulation results show that the proposed heuristic performs better than other existing heuristics at a significantly reduced total weighted tardiness. <s> BIB046 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Many real scheduling problems are often much more complex than problems that are analytically tractable. The main difficulty in obtaining optimal job schedules arises from the existence of sequence dependent setup times among jobs and job release times. In this paper, we present a restricted tabu search algorithm that schedules jobs on parallel machines in order to minimise the maximum lateness of the jobs. The jobs have release times and due dates, and sequence-dependent setup times exist between the jobs. The parallel machines are either identical or non-identical in terms of the processing times of the jobs. The restricted tabu search algorithm employs a restricted search with the elimination of non-effective job moves, for finding the best neighbourhood schedule. The restricted search algorithm reduces search effort significantly while obtaining good quality final schedule. The experimental results show that the proposed algorithm obtains much better solutions more quickly than other heuristic algorithms such as the Rolling Horizon Procedure (RHP) heuristic, the basic tabu search and simulated annealing. <s> BIB047 </s> A survey of scheduling problems with setup times or costs <s> Non-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> BIB048 </s> A survey of scheduling problems with setup times or costs <s> Non-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> BIB049 </s> A survey of scheduling problems with setup times or costs <s> Non-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> BIB050 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> This paper attempts to solve a single machine scheduling problem (n|l|r(subscript i), s(subscript ij)|∑w(subscript i)T(subscript i)), in which the objective function is to minimize the total weighted tardiness with different release dates and sequence-dependent setup times. There is not a mathematical programming or a heuristic method for this type of problem up to now. In this study, we propose a heuristic scheduling algorithm with the complexity of O(n^3)to solve this problem. To validate the performance of the heuristic proposed herein, a mathematical programming with logical constraints model is also formulated. Experimental results show that this algorithm can find10321 optimal solutions out of 12600 randomly generated problems. Total average solution quality is 98.03%. A11-Job case(large problem)requires only 0.00065 seconds, on average, to obtain an ultimate solution. The results demonstrate that the heuristic scheduling algorithm can efficiently solve this kind of problem. <s> BIB051 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> The single-machine early/tardy (E/T) scheduling problem is addressed in this research. The objective of this problem is to minimize the total amount of earliness and tardiness. Earliness and tardiness, are weighted equally and the due date is common and large (unrestricted) for all jobs. Machine setup time is included and is considered sequence-dependent. When sequence-dependent setup times are included, the complexity of the problem increases significantly and the problem becomes NP-hard. In the literature, only mixed integer programming formulation is available to optimally solve the problem at hand. In this paper, a branch-and-bound algorithm (B&B) is developed to obtain optimal solutions for the problem. As it will be shown, the B&B solved problems three times larger than what has been reported in the literature. <s> BIB052 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Extensive research has been devoted to preemptive scheduling. However, little attention has been paid to problems where a certain time penalty must be incurred if preemption is allowed. In this paper, we consider the single-machine scheduling problem of minimizing the total completion time subject to job release dates and preemption penalties, where each time a job is started, whether initially or after being preempted, a job-independent setup must take place. The problem is proved to be strongly NP-hard even if the setup time is one unit. We also study a natural extension of a greedy algorithm, which is optimal in the absence of preemption penalty. It is proved that the algorithm has a worst-case performance bound of 25/16, even when the maximum completion time, i.e., makespan, criterion is considered simultaneously. <s> BIB053 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Flexibility, speed, and efficiency are major challenges for operations managers in today's knowledge-intensive organizations. Such requirements are converted into three production scheduling criteria: (a) minimize the impact of setup times in flexible production lines when moving from one product to another, (b) minimize number of tardy jobs, and (c) minimize overall production time, or makespan, for a given set of products or services. There is a wide range of solution methodologies for such NP-hard scheduling problems. While mathematical programming models provide optimal solutions, they become too complex to model for large scheduling problems. Simultaneously, heuristic approaches are simpler and very often independent of the problem size, but provide "good" rather than optimal solutions. This paper proposes and compares two alternative solutions: 0-1 mixed integer linear programming and genetic programming. It also provides guidelines that can be used by practitioners in the process of selecting the appropriate scheduling methodology. <s> BIB054 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> The problem is to minimize the total weighted completion time on a single batch-processing machine with setup times. The machine can process a batch of at most B jobs at one time, and the processing time of a batch is given by the longest processing time among the jobs in the batch. The setup time of a batch is given by the largest setup time among the jobs in the batch. This batch-processing problem reduces to the ordinary uni-processor scheduling problem when B = 1. In this paper we focus on the extreme case of B = +∞, i.e. a batch can contain any number of jobs. We present in this paper a polynomial-time approximation algorithm for the problem with a performance guarantee of 2. We further show that a special case of the problem can be solved in polynomial time. <s> BIB055 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Abstract In this paper we consider the problem of creating batches of parts, to be processed in a flexible manufacturing cell, and scheduling their operations. We consider the case in which the system consists of one machine and at most k parts may be present in the system at the same time. Given that each part requires a sequence of operations, and each operation requires a given tool, the objective is to minimize the total number of setups. We develop a heuristic algorithm for its solution and we present an extensive computational experience. <s> BIB056 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Abstract A single machine batch scheduling problem is addressed. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time common for all batches. Two external resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource and the job processing times are jointly compressible by another resource, i.e., the amount of resource consumption for setup time compression is the same for all setups and the amount of resource consumption for job processing time compression is the same for all jobs. Polynomial time algorithms are presented to find an optimal batch sequence and optimal amounts of resource consumption such that either total job completion time is minimized, subject to an upper bound on total weighted resource consumption, or total weighted resource consumption is minimized, subject to an upper bound on total job completion time. The algorithms are based on results from linear programming and from batch scheduling with fixed setup and processing times. <s> BIB057 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> We apply group technology on a single-facility scheduling problem of products assembled from common and unique components. Our model assumes that common components are classified into multiple families, whose set-up times are sequence-independent but not identical. This extension from one type of common components to multiple types distinguishes this study from those in the literature. After identifying properties for dominant schedules, a branch-and-bound algorithm is constructed to determine a production schedule with the minimum total completion time of products. A series of simulation experiments are made with respect to the number of families and the number of products. The outcome may provide a foundation for future research on this topic. <s> BIB058 </s> A survey of scheduling problems with setup times or costs <s> Non-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> BIB059 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> The one-machine scheduling problem with sequence-dependent setup times and costs and earliness-tardiness penalties is addressed. A time-indexed formulation of the problem is presented as well as different relaxations that give lower bounds of the problem. Then, a branch-and-bound procedure based on one of these lower bounds is presented. The efficiency of this algorithm also relies on new dominance rules and on a heuristic to derive good feasible schedules. Computational tests are finally presented. <s> BIB060 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> In this paper we propose a robust approach for solving the scheduling problem of parallel machines with sequence-dependent set-up costs. In the literature, several mathematical models and solution methods have been proposed to solve such scheduling problems, but most of which are based on the strong assumption that input data are known in a deterministic way. In this paper, a fuzzy mathematical programming model is formulated by taking into account the uncertainty in processing times to provide the optimal solution as a trade-off between total set-up cost and robustness in demand satisfaction. The proposed approach requires the solution of a non-linear mixed integer programming (NLMIP), that can be formulated as an equivalent mixed integer linear programming (MILP) model. The resulting MILP model in real applications could be intractable due to its NP-hardness. Therefore, we propose a solution method technique, based on the solution of an approximated model, whose dimension is remarkably reduced with respect to the original counterpart. Numerical experiments conducted on the basis of data taken from a real application show that the average deviation of the reduced model solution over the optimum is less than 1.5%. <s> BIB061 </s> A survey of scheduling problems with setup times or costs <s> Non-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> BIB062 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> Abstract In this study, we consider the problem of scheduling a set of independent jobs with sequence-dependent setup times and job splitting, on a set of identical parallel machines such that maximum completion time (makespan) is minimized. For this NP-hard problem, we suggest a heuristic algorithm improving an existing one, using a linear programming modeling with setup times and job splitting considerations. The performance of our new method is tested on over 6000 instances with different size by comparing it with a lower bound. <s> BIB063 </s> A survey of scheduling problems with setup times or costs <s> Non-batch sequence-dependent setup times <s> In this paper, we study the multi-machine scheduling problem with earliness and tardiness penalties and sequence dependent setup times. This problem can be decomposed into two subproblems—sequencing and timetabling. Sequencing focuses on assigning each job to a fixed machine and determine the job sequence on each machine. We call such assignment a semi-schedule. Timetabling focuses on finding an executable schedule from the semi-schedule via idle-time insertion. Sequencing is strongly NP-hard in general. Although timetabling is polynomial-time solvable, it can become a computational bottleneck if the procedure is executed many times within a larger framework. This paper makes two contributions. We first propose a quantum improvement to the computational efficiency of the timetabling algorithm. We then apply it within a squeaky wheel optimization framework to solve the sequencing and overall problem. Finally, we demonstrate the strength of our proposed algorithms by experiments. Copyright Springer Science+Business Media, LLC 2008 <s> BIB064
The 1=ST sd = P T j problem was addressed in a number of papers. BIB001 proposed a simulated annealing algorithm and showed by computational analysis that it performs better than earlier algorithms. Different versions of genetic algorithms were proposed by BIB020 , BIB021 and BIB029 . BIB037 proposed an Ant Colony Optimization (ACO) algorithm for the same problem and showed that it performs competitively with the best results of BIB021 in terms of solution quality while it takes less computational time.  presented a multi start procedure, which is a simple algorithm that creates an initial random solution and then applies a local search procedure repeatedly to the obtained initial solution.  proposed two heuristics, a greedy randomized adaptive search procedure (GRASP) and a problem space-based local search heuristic. They showed that the problem spacebased local search heuristic performs equally well when compared to ACO of BIB037 while taking much less computational time.  also showed that GRASP gives much better solutions than ACO while it takes much more computation time than ACO. However, the genetic versions of BIB020 , BIB021 , and BIB029 remain to be compared with one another. BIB051 proposed a mathematical programming model with logical constraints for the problem of 1=ST sd ; r j = P w j T j . They also proposed a heuristic algorithm and conducted computational experiments, which revealed that the heuristic can efficiently solve the problem. For the common due date case, BIB052 proposed a branch-and-bound algorithm for the 1=ST sd = P E j þ P T j problem, where they showed that problems with up to 25 jobs can be solved by the algorithm in a reasonable time.  considered the single machine earliness-tardiness scheduling problem, where they proposed a hybrid genetic algorithm with the objective of minimizing a penalty function that includes a penalty for completing a job early or tardy, and a penalty for the total setup time between the jobs. BIB010 proposed a hybrid genetic algorithm for the problem with the objective of minimizing the sum of setup costs in addition to inventory and backlog costs. They showed that the performance of the hybrid algorithm is much better than that of the pure genetic algorithm.  considered the 1=ST sd =k P C j þ ð1 À kÞ P T j problem where the objective is to minimize a weighted sum of total completion time and total tardiness. They developed an integer programming model for the problem. Moreover, they presented a simple heuristic and used this heuristic as an initial solution for their proposed Tabu search algorithm. BIB011 proposed a branch-andbound algorithm for the 1/ST sd , r j /T max problem, where the machine may not be available for certain BIB002 Effect of batch sizes on setup utilization (total setup time divided by total setup and processing time) in a queuing delay batching model An upper bound of 3-2 p 2 on optimal setup utilization, batch sizes should be corrected if setup utilization is higher than the bound BIB012 L max , P w j C j (maintenance is performed on the machine periodically) NP-complete of the problem, dynamic programming BIB038 Meeting deadlines (r j , preemption) NP-hard in the strong sense, dynamic programming, an approximation scheme BIB053 P C j (r j , constant setup time, preemption) NP-hard in the strong sense, worst-case performance ratio ST sd /SC sd Tan and Narasimhan (1997) P T j Simulated annealing  Minimize a penalty function including penalties of early-tardy and total setup time Hybrid genetic algorithm Kolahan and Liang (1998) P w j E j þ P w j T j þ ðlinear costs for compression or extension of job processing timesÞ Tabu search BIB011 T max (r j , machine unavailability for certain periods) Branch-and-bound, algorithm BIB010 BIB039 L max (r j ) Tabu search BIB051 P w j T j (r j ) Mathematical programming, heuristic BIB054 C max and P U j (dual criteria) Mixed-integer programming, genetic algorithm BIB052 P E j þ P T j (common due date) Branch-and-bound algorithm  k P C j þ ð1 À kÞ P T j Integer programming, Tabu search  P T j A greedy randomized adaptive search procedure, a space-based local search heuristic Koulamas and Kyparisis (in press) C max , RC j , the total absolute differences in completion times (setup times are proportionate to the length of the already scheduled jobs) A sorting procedure BIB003 Find an optimal common due date, and minimize the sum of the costs of tardy jobs (also considers the case of group technology) Conditions for the optimality, polynomial time algorithm Liaee and Emmons (1997) P U j (Group technology) NP-hard  L max Lower bound, branch-and-bound BIB005 P f j (subject to due date constraints, group technology) Presents a polynomial time algorithm BIB006 P w j E j þ P w j T j (common due date) Genetic algorithm BIB007 D max Dynamic programming BIB008 P C i (a job is attributed a family and an order) Branch-and-bound algorithm BIB013 L max (common setup time) Heuristic P U j (Group technology) NP-hard in the strong sense (even for the unit processing time and zero setup times) BIB014 P w j f j , P w j T j , and L max in expected sense (processing times and due dates are random variables, consider also group technology) Derives conditions under which the deterministic results are optimal BIB022 L max Dominance properties, branch-and-bound algorithm BIB023 P w j f j Branch-and-bound algorithm BIB030 P U j Strongly NP-hard BIB031 L max Heuristic, integer programming  P f j (major and minor setup times) Tabu search BIB040 L max (Group technology, major and minor setup times) Integer programming, tabu search based heuristic BIB040 L max (major and minor setup times) Mixed-integer programming, tabu searchbased heuristic BIB043 L max Strongly NP-hard BIB044 P w j E j þ P w j T j (common due date) Necessary optimal conditions, heuristic, genetic algorithm Schaller (in press) P T j (consider also group technology) Branch-and-bound, heuristic Schaller and Gupta (in press ) P E j þ P T j (consider also group technology) Branch-and-bound, heuristic Yang and Chand (in press ) P C j (processing times change based on their positions in a schedule) Lower bound, branch-and-bound ST sd,b /SC sd,b  C max Traveling salesman problem, polynomial time algorithm P w j T 2 j (r j ) Lagrangian relaxation based approach, tabu search, simulated annealing BIB055 P w j C j (batch setup and processing times are equal to the maxima of job setup and processing times, respectively, in the batch) 2-Approximation, computational complexity is open  Minimize a regular sum of objective functions (r j , setup times and costs) Lower bounds, dominance properties, branch-and-bound BIB059 Minimize average tardiness and cycle time, maximize machine utilization Pareto optimal solution, simulation Karabati and Akkan (2006) P C j Branch-and-bound BIB060 Minimize the sum of earliness-tardiness and setup costs Branch-and-bound, dominance rules, heuristic BIB062 Minimize the sum of earliness-tardiness and setup costs NP-hardness, pseudo polynomial algorithm (continued on next page)  , dynamic programming BIB015 T max (r j , p j = p) O ( n 14 log n), dynamic programming BIB024 P U i (standard and specific components, batching for standard components) NP-hard, O(n 2 d max ), d max is the maximum due date, dynamic programming BIB016 L max (standard and specific components, batching for standard components) O(n log n), dynamic programming BIB017 P T j O(n 11 M 7 ) dynamic programming, M is maximum numerical parameter BIB032 L max (an upper bound on total weighted resource consumption), and total weighted resource consumption (job deadlines) Polynomial algorithms, linear programming with two variables BIB033 Various regular objectives (constant number k of distinct job processing times or due dates) Algorithms polynomial in n and exponential in k, dynamic programming BIB045 P C j (an upper bound on total weighted resource consumption), and an inverse problem. Job and batch dependent resources. Agreeable job processing time bounds. BIB056 TSC (tool loading) Heuristic BIB057 P C j (an upper bound on total weighted resource consumption) and an inverse problem Polynomial algorithms, linear programming with two variables BIB058 P C j (standard and specific components, batching for standard components) Branch-and-bound algorithm  L max (precedence constraints, r j , p j = p) O ( n 2 ) time reduction to the problem without precedence constraints P C j (p j = p) O ( n), rounding optimal non-integer batch sizes Yuan et al. (in press-b) P w j C j (common setup times, common batch sizes) Strongly NP-hard even if the batch size = 3 and the weight of each job = its processing times Mosheiov and Oron (in pressa) They showed that their algorithm obtains a much better solution than existing heuristics in less computational time. BIB054 presented a mixed integer programming and a genetic algorithm for the 1/ST sd problem with the minimization of P U j as the primary objective, and the minimization of the C max as the secondary objective. They concluded that the integer programming becomes very complex and unmanageable when the number of jobs is more than ten. They also stated that the computational analysis showed that the proposed genetic algorithm performs better when the ratio of setup times to processing times is relatively large. BIB009 presented a tabu search approach to a just-in-time scheduling problem with sequence dependent setup times, in which there are linear costs for compression or extension of job processing times. The objective is a linear combination of the total weighted earliness and tardiness, and the total weighted compression and extension costs. Koulamas and Kyparisis (in press ) considered the single machine scheduling problem with setup times that are proportionate to the length of the already scheduled jobs, which they call pastsequence dependent setup times. They showed that the single machine problem with the objective functions of makespan, total completion time, total absolute differences in completion times, and a linear combination of the last two objective functions can be solved in O(n log n) time by a sorting procedure. Heady and Zhu (1998) addressed the P/ST sd problem, where some machines may not be able to process some jobs. They proposed a heuristic to minimize the sum of earliness and tardiness costs for the problem. For small-sized problems, they also compared the performance of the proposed heuristic with the optimal solution obtained from using integer programming formulation. BIB018 considered the P/ST sd , r j problem, where there are two types of machines, both processing and setup times depend on the machines, and each job has a release date and a due date. The objective is to find a feasible schedule first and then to minimize the cost due to assignment and setup times. They proposed a hybrid method that consists of an iterative heuristic, a genetic algorithm, and a branch-and-bound algorithm. BIB025 addressed the P =ST sd = P E j þ P T j problem, presented a mathematical programming formulation that can be used for limited-sized problems, and proposed a simulated annealing algorithm for large-sized  C max Heuristics, tabu search  C max , P w j T j , P w j C j (r j ) Genetic algorithm BIB046 P w j T j Heuristic, tabu search BIB047 L max (r j , both identical and non-identical machine cases) problems. BIB064 addressed the more general P =ST sd = P w j E j þ P w j T j problem and proposed a meta-heuristic called Squeaky Wheel Optimization. BIB064 showed that their heuristic outperforms that of Radhakrishnan and Ventura. BIB041 considered the P/ST sd BIB048 P w j C j , P w j U j Branch-and-bound algorithm BIB049 P w j T j (R, multioperational jobs, operations of the same job can be processed concurrently) Constructive heuristics and simulated annealing BIB050 C max (a job can be split into several parts to be processed concurrently) Heuristic based on a reduction to traveling salesman problem  P w j T j (r j , calendar constraint) Simulated annealing, new neighborhood mechanisms problem with the objective of maximizing the weighted number of jobs that are completed at their due dates. They showed that some special cases of the problem are polynomially solvable while the problem is NP-hard in general.  and BIB034 addressed the P/ST sd /C max problem.  proposed two heuristics, namely one tabu search based and the other a memetic approach that is a combination of a population based method with local search procedures. BIB034 proposed lower bounds and presented a divide and merge heuristic. They compared their heuristic with earlier heuristics of tabu search and showed that their heuristic is much faster while producing similar quality results. BIB063 addressed the same problem of P/ST sd /C max with job splitting. Job splitting is different from preemption in that jobs can be split and processed simultaneously on different machines. They proposed a heuristic based on linear programming modeling. The performance of their proposed method was tested on problems of different sizes by comparing the solutions of the method with a lower bound. BIB026 addressed the P/ ST sd , prec/C max problem, where they considered the problem as a combination of two parts, namely, partitioning and sequencing. They established that the problem is strongly NP-hard where the starting times respect a given order for the case of no precedence relations. Fixing the sequencing problem first, they showed that it is unlikely that an efficient list scheduling algorithm exists that leads to a dominant set of schedules. As a result, they concluded that the problem cannot be solved by considering only the decisions for one of its two parts as the solution space and solving the remaining sub-problem afterwards. BIB035 presented an integer programming formulation for the problem of P/ ST sd , r j /C max . They also developed several heuristics including a genetic algorithm and multi-fit based approaches and empirically evaluated them. They used solution of the traveling salesman problem (TSP) as part of their heuristics. That is, once the jobs have been assigned to the machines, a TSP is formulated and solved to find an optimal job sequence on each machine. In the TSP, the (asymmetric) distances correspond to the (sequence dependent) setup times. BIB047 proposed a restricted tabu search algorithm for the P/ ST sd , r j /L max problem for both cases of identical and non-identical machines. The restricted search algorithm reduces the search effort significantly without eliminating promising solutions. BIB036 addressed the R=ST sd = P w j C j problem. They presented seven simple heuristics for the problem and showed by computational experiments that one of them outperforms the others. The best heuristic assigns one job at a time based on the smallest ratio of a job's processing time plus setup time to its weight.  proposed a hybrid genetic algorithm for the P =ST sd ; r j = P w j C j , P =ST sd ; r j = P w j T j , and P/ST sd , r j /C max problems. In the hybrid genetic algorithm, a genetic algorithm is used to assign jobs to machines, and dispatching rules are used to schedule the individual machines. Computational results indicated that the proposed hybrid approach performs better than earlier algorithms with respect to the considered performance measures. The P =ST sd ; r j = P C j problem was addressed by  . They presented a necessary and sufficient condition for a local optimal solution and proposed a heuristic that is based on the condition. They also developed a lower bound. The quality of their heuristic was tested on randomly generated problems by comparing the heuristic solution with a developed lower bound. Clearly, the genetic algorithm of  and the heuristic proposed by  remain to be compared.  proposed a genetic algorithm for the Q=ST sd = P w j T j problem. In their genetic algorithm, they dynamically modified the mutation rate, crossover rate, and insertion rate. BIB027 proposed the use of a neural network to obtain values for the parameters in calculating a priority rule for the P =ST sd = P w j T j problem. Their computational results indicated that their proposed approach outperforms that of an earlier approach. BIB046 presented a heuristic for the same problem, which consists of four phases, where the third phase is a tabu search. A comparison of the genetic algorithm presented by  and the hybrid heuristic proposed by BIB046 remains to be performed.  presented a tabu search algorithm for the P =ST sd ; r j = P T j problem. They investigated several key components of tabu search and identified the best values for these components. They compared their heuristic with the genetic algorithm of Sivrikaya-Serifoglu and Ulusoy (1999) for the case of zero weight for earliness, and showed that their heuristic outperforms that of Sivrikaya-Serifoglu and Ulusoy (1999). Sivrikaya-Serifoglu and Ulusoy (1999) addressed the problem of Q=ST sd ; r j =w E P E j þ w T P T j , where there are two types of machines with different speeds. Here w E P E j þ w T P T j means that the weights for earliness and tardiness penalties are common to all the jobs. Sivrikaya-Serifoglu and Ulusoy (1999) presented two types of genetic algorithms, namely one with a crossover operator and one without crossover operator. They showed that the genetic algorithm with a crossover operator performs better for difficult and large-sized problems. BIB019 considered the general case of uniform machines with the objective function of minimizing P w j E j þ P w j T j . They presented a mixed integer programming formulation for the problem. BIB028 addressed the R=ST sd = P w j E j þ P w j T j problem. They developed a mixed integer programming formulation for the problem, which can provide an optimal solution in reasonable time for nine jobs and three machines. The P/SC sd problem with the objective of minimizing the total setup costs was considered by BIB061 . They considered the case where the job processing times are uncertain, and proposed a fuzzy mathematical programming approach to solve the problem. They also showed that the problem can be converted into a mixed integer linear programming model. Moreover, they proposed an approximation model that can be used to handle larger problems and showed that the average deviation of the approximation model solution over the optimal solution is less than 1.5%. proved the ordinary NP-hardness and presented a pseudopolynomial time algorithm for the multiple family problem P 2=ST si;b ; p j ¼ p= P C j with a common setup time. BIB004 proved the ordinary NP-hardness of the same problem under the group technology assumption unless all the families contain the same number of jobs. BIB042 proved the strong NP-hardness of the problem P =ST si;b = P C j under the group technology assumption, and presented a polynomial-time dynamic programming algorithm for the special case with a given number of the machines. Leung et al. (in press ) considered the problem Pm=ST si;b ¼ s= P C j , where the processing time of each job is a step function of its waiting time, i.e., the time between the start of the processing of the batch to which the job belongs and the start of the processing of the job. For each job i, if its waiting time is less than a given threshold D, then it requires a basic processing time p i = a i ; otherwise, it requires an extended processing time p i = a i + b i . They proved that this problem is NP-hard in the strong sense, even if there is only one machine and b i = b for all i = 1,. . . , n; and is polynomially solvable, if b i = b for all i = 1,. . . , n. An approximation algorithm with performance guarantee 2 was given for the case b i 6 D, i = 1,. . . , n. 