A survey of scheduling problems with setup times or costs
---
paper_title: SOFT COMPUTING FOR SCHEDULING WITH BATCH SETUP TIMES AND EARLINESS-TARDINESS PENALTIES ON PARALLEL MACHINES

paper_content:

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.
---
paper_title: An integrated system solution for supply chain optimization in the chemical process industry

paper_content:

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.
---
paper_title: Unrelated parallel machine scheduling with setup times using simulated annealing

paper_content:

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.
---
paper_title: Scheduling a flowline manufacturing cell with sequence dependent family setup times

paper_content:

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.
---
paper_title: A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times

paper_content:

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.
---
paper_title: A case study in a two-stage hybrid flow shop with setup time and dedicated machines

paper_content:

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.
---
paper_title: A review of flowshop scheduling research with setup times

paper_content:

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.
---
paper_title: Scheduling with batching: A review

paper_content:

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.
---
paper_title: Survey of scheduling research involving setup times

paper_content:

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.
---
paper_title: Genetic algorithms applied in BOPP film scheduling problems: minimizing total absolute deviation and setup times

paper_content:

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.
---
paper_title: Cost models for lot streaming in a multistage flow shop

paper_content:

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.
---
paper_title: Constructing Near Optimal Schedules for the Flow-Shop Lot Streaming Problem with Sublot-Attached Setups

paper_content:

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.
---
paper_title: Scheduling jobs on parallel machines applying neural network and heuristic rules

paper_content:

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.
---
paper_title: A heuristic to minimize the total weighted tardiness with sequence-dependent setups

paper_content:

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.
---
paper_title: The capacitated lot sizing problem: a review of models and algorithms

paper_content:

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.
---
paper_title: Group technology in a hybrid flowshop environment: A case study

paper_content:

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.).
---
paper_title: Lot sizing and scheduling — Survey and extensions

paper_content:

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.
---
paper_title: Scheduling with batching: A review

paper_content:

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.
---
paper_title: Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

paper_content:

The theory of deterministic sequencing and scheduling has expanded rapidly during the past years. In this paper we survey the state of the art with respect to optimization and approximation algorithms and interpret these in terms of computational complexity theory. Special cases considered are single machine scheduling, identical, uniform and unrelated parallel machine scheduling, and open shop, flow shop and job shop scheduling. We indicate some problems for future research and include a selective bibliography.
---
paper_title: Minimizing Total Completion Time Subject to Job Release Dates and Preemption Penalties

paper_content:

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.
---
paper_title: Scheduling Maintenance and Semiresumable Jobs on a Single Machine

paper_content:

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
---
paper_title: Scheduling with job release dates, delivery times and preemption penalties

paper_content:

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.
---
paper_title: A note on the complexity of family scheduling to minimize the number of late jobs

paper_content:

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.
---
paper_title: Stochastic sequencing with job families, set-up times, and due dates

paper_content:

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.
---
paper_title: EARLINESS/TARDINESS SCHEDULING WITH A COMMON DUE DATE AND FAMILY SETUPS

paper_content:

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.
---
paper_title: Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming

paper_content:

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.
---
paper_title: A heuristic approach for single-machine scheduling with due dates and class setups

paper_content:

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.
---
paper_title: Single machine scheduling with common due date assignment in a group technology environment

paper_content:

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.
---
paper_title: Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective

paper_content:

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.
---
paper_title: Optimal scheduling of two-component products on a single facility

paper_content:

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.
---
paper_title: A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times

paper_content:

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.
---
paper_title: A due date density-based categorising heuristic for parallel machines scheduling

paper_content:

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.
---
paper_title: List Scheduling in a Parallel Machine Environment with Precedence Constraints and Setup Times

paper_content:

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.
---
paper_title: A genetic algorithm for scheduling on a single machine with set-up times and due dates

paper_content:

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.
---
paper_title: The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard

paper_content:

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.
---
paper_title: A genetic algorithm for scheduling job families on a single machine with arbitrary earliness/tardiness penalties and an unrestricted common due date

paper_content:

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.
---
paper_title: Setup utilization as a performance indicator in production planning and control

paper_content:

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.
---
paper_title: A Heuristic Algorithm to Minimize Total Weighted Tardiness on a Single Machine with Release Dates and Sequence-Dependent Setup Times

paper_content:

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.
---
paper_title: Minimizing the sum of earliness/tardiness in multi-machine scheduling: a mixed integer programming approach

paper_content:

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.
---
paper_title: A Tabu Search Algorithm for Single Machine Scheduling with Release Times, Due Dates, and Sequence-Dependent Set-up Times

paper_content:

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.
---
paper_title: The complexity of two group scheduling problems

paper_content:

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.
---
paper_title: Lower bounds and algorithms for flowtime minimization on a single machine with set-up times

paper_content:

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.
---
paper_title: An adaptive TS approach to JIT sequencing with variable processing times and sequence-dependent setups

paper_content:

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.
---
paper_title: Heuristic procedures for scheduling Job Families with Setups and Due Dates

paper_content:

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
---
paper_title: A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times

paper_content:

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.
---
paper_title: Heuristic scheduling of parallel machines with sequence-dependent set-up times

paper_content:

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...
---
paper_title: Single machine group scheduling to minimize mean flow time subject to due date constraints

paper_content:

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.
---
paper_title: Scheduling families of jobs with setup times

paper_content:

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.
---
paper_title: Robust scheduling of parallel machines with sequence-dependent set-up costs

paper_content:

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%.
---
paper_title: Batching and sequencing of jobs with order availability at a single facility

paper_content:

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.
---
paper_title: Earliness-tardiness scheduling with setup considerations

paper_content:

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.
---
paper_title: Comparing an ACO algorithm with other heuristics for the single machine scheduling problem with sequence-dependent setup times

paper_content:

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.
---
paper_title: Minimizing maximum lateness with job families

paper_content:

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.
---
paper_title: An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times

paper_content:

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.
---
paper_title: A comparison of four methods for minimizing total tardiness on a single processor with sequence dependent setup times

paper_content:

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.
---
paper_title: A memetic algorithm for the total tardiness single machine scheduling problem

paper_content:

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.
---
paper_title: A hybrid method for a parallel-machine scheduling problem

paper_content:

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.
---
paper_title: Minimizing Total Completion Time Subject to Job Release Dates and Preemption Penalties

paper_content:

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.
---
paper_title: A Hybrid Genetic Algorithm for the Single Machine Scheduling Problem

paper_content:

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.
---
paper_title: A branch-and-bound algorithm for the early/tardy machine scheduling problem with a common due-date and sequence-dependent setup time

paper_content:

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.
---
paper_title: Improved dynamic programs for some batching problems involving the maximum lateness criterion

paper_content:

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.
---
paper_title: Dynasearch for the earliness–tardiness scheduling problem with release dates and setup constraints

paper_content:

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.
---
paper_title: On Minimizing Total Tardiness In A Serial Batching Problem

paper_content:

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.
---
paper_title: A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times

paper_content:

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.
---
paper_title: Efficient algorithms for machine scheduling problems with earliness and tardiness penalties

paper_content:

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
---
paper_title: Exact algorithms for scheduling multiple families of jobs on parallel machines

paper_content:

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.
---
paper_title: Batching Identical Jobs

paper_content:

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.
---
paper_title: Scheduling with shutdowns and sequence dependent set-up times

paper_content:

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...
---
paper_title: Scheduling of parallel identical machines to maximize the weighted number of just-in-time jobs

paper_content:

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.
---
paper_title: Batch scheduling with controllable setup and processing times to minimize total completion time

paper_content:

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.
---
paper_title: Single machine batch scheduling with jointly compressible setup and processing times

paper_content:

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.
---
paper_title: Single machine batch scheduling with sequential job processing

paper_content:

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...
---
paper_title: Scheduling jobs on parallel machines applying neural network and heuristic rules

paper_content:

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.
---
paper_title: Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

paper_content:

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.
---
paper_title: Early/tardy scheduling with sequence dependent setups on uniform parallel machines

paper_content:

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.
---
paper_title: Multi-objective scheduling of two-job families on a single machine

paper_content:

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.
---
paper_title: Batch-processing scheduling with setup times

paper_content:

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.
---
paper_title: Minimizing tardiness on a single processor with sequence-dependent setup times: a simulated annealing approach

paper_content:

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.
---
paper_title: Scheduling Maintenance and Semiresumable Jobs on a Single Machine

paper_content:

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
---
paper_title: Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times

paper_content:

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.
---
paper_title: Scheduling jobs on parallel machines: a restricted tabu search approach

paper_content:

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.
---
paper_title: Single machine batch scheduling with resource dependent setup and processing times

paper_content:

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.
---
paper_title: Scheduling the production of two-component jobs on a single machine

paper_content:

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.
---
paper_title: Scheduling with job release dates, delivery times and preemption penalties

paper_content:

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.
---
paper_title: Scheduling to minimize the maximum lateness with multiple product classes in batch processing

paper_content:

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.
---
paper_title: A heuristic approach to batching and scheduling a single machine to minimize setup costs

paper_content:

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.
---
paper_title: A note on the complexity of family scheduling to minimize the number of late jobs

paper_content:

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.
---
paper_title: Stochastic sequencing with job families, set-up times, and due dates

paper_content:

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.
---
paper_title: EARLINESS/TARDINESS SCHEDULING WITH A COMMON DUE DATE AND FAMILY SETUPS

paper_content:

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.
---
paper_title: On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times

paper_content:

We consider the single machine, serial batching, total completion time scheduling problem with precedence constraints, release dates and identical processing times in this paper. The complexity of this problem is reported as open in the literature. We provide an O(n^5) time algorithm to solve this problem.
---
paper_title: A heuristic approach for single-machine scheduling with due dates and class setups

paper_content:

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.
---
paper_title: Single machine scheduling with common due date assignment in a group technology environment

paper_content:

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.
---
paper_title: Strong NP-hardness of the single machine multi-operation jobs total completion time scheduling problem

paper_content:

We consider the single machine multi-operation jobs total completion time scheduling problem. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a set-up time. A job completes when all of its operations have been processed. The objective is to minimize the sum of the job completion times. In the literature, the computational complexity of this problem is posed as open. We show that the problem is strongly NP-hard even when the set-up times are common and the processing time of each operation is 0 or 1.
---
paper_title: Optimal scheduling of two-component products on a single facility

paper_content:

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.
---
paper_title: Fabrication scheduling on a single machine with due date constraints

paper_content:

Abstract There is a fabrication machine available for processing a set of jobs. Each job is associated with a due date and consists of two parts, one is common among all products and the other is unique to itself. The unique components are processed individually and the common parts are grouped into batches for processing. A constant setup time is incurred when each batch is formed. The completion time of a job is defined as the time when both of its unique and common components are completed. In this paper, we consider two different objectives. The first problem seeks to minimize the maximum tardiness, and the second problem is to minimize the number of tardy jobs. To minimize the maximum tardiness, we propose a dynamic programming algorithm that optimally solves the problem in polynomial time. Next, we show NP-hardness proof and design a pseudo-polynomial time dynamic programming algorithm for the problem of minimizing the number of tardy jobs.
---
paper_title: The single machine batching problem with family setup times to minimize maximum lateness is strongly NP-hard

paper_content:

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.
---
paper_title: A genetic algorithm for scheduling job families on a single machine with arbitrary earliness/tardiness penalties and an unrestricted common due date

paper_content:

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.
---
paper_title: The CLWS heuristic for single machine scheduling problem

paper_content:

Abstract A model for real-time control of flexible manufacturing systems is considered. In this model, a machine can process a finite number of part types at specified rates, but only one part type can be processed at any given time. Each switch from one type to another requires setup time. The clear-the-largest-work-after-setup (CLWS) heuristic policy which stabilizes the system in the sense that, in the long run, the required demand is met, has been introduced. That way, a better upper bound on the total work backlog than those available in earlier literature is derived. Computational results for the case of finite horizon show that the error of the heuristic CLWS from the optimal solution is 2.5–3.0% on average. Some computational results that compare the CLWS heuristic to the heuristic available in the earlier literature, for the same problem, are also reported.
---
paper_title: Setup utilization as a performance indicator in production planning and control

paper_content:

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.
---
paper_title: Lower bounds and algorithms for flowtime minimization on a single machine with set-up times

paper_content:

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.
---
paper_title: Heuristic procedures for scheduling Job Families with Setups and Due Dates

paper_content:

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
---
paper_title: Single machine group scheduling to minimize mean flow time subject to due date constraints

paper_content:

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.
---
paper_title: Scheduling families of jobs with setup times

paper_content:

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.
---
paper_title: A note on the single machine serial batching scheduling problem to minimize maximum lateness with precedence constraints

paper_content:

We consider the single machine, serial batching, maximum lateness scheduling problem with precedence constraints in this paper. The complexity of this problem is reported as open in the literature. We give an O(n^2) polynomial-time algorithm for this problem.
---
paper_title: Batching and sequencing of jobs with order availability at a single facility

paper_content:

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.
---
paper_title: Minimizing maximum lateness with job families

paper_content:

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.
---
paper_title: Minimizing L max for the single machine scheduling problem with family set-ups

paper_content:

A procedure for the single machine-scheduling problem of minimizing the maximum lateness for jobs with sequence independent set-ups is presented. The procedure provides optimal/near-optimal solutions over a wide range of problems. It performs well compared with other heuristics, and it is effective in finding solutions for large problems.
---
paper_title: Scheduling of Customized Jobs on a Single Machine under Item Availability

paper_content:

We study a problem of scheduling customized jobs on a single-machine. Each job requires two operations: one standard and one specific. Standard operations are processed in batches under item availability, and each batch requires a set-up time. Based on structural properties of the optimal solution, we introduce a generic dynamic programming scheme that builds an optimal schedule by alternately inserting blocks of operations of two distinct types. Our approach yields efficient algorithms for the sum of completion times problem with agreeable processing times and the maximum lateness problem. The number of late jobs problem is shown to be NP-hard in the ordinary sense, but is pseudo-polynomially solvable. A polynomial algorithm is also given for a special case of this problem. Our results indicate the differences between this problem and its counterpart under batch availability.
---
paper_title: Improved dynamic programs for some batching problems involving the maximum lateness criterion

paper_content:

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.
---
paper_title: On Minimizing Total Tardiness In A Serial Batching Problem

paper_content:

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.
---
paper_title: Single machine group scheduling with resource dependent setup and processing times

paper_content:

A single machine scheduling problem is studied. There is a partition of the set of n jobs into g groups on the basis of group technology. Jobs of the same group are processed contiguously. A sequence independent setup time precedes the processing of each group. Two external renewable resources can be used to linearly compress setup and job processing times. The setup times are jointly compressible by one resource, the job processing times are jointly compressible by another resource and the level of the resource is the same for all setups and all jobs. Polynomial time algorithms are presented to find an optimal job sequence and resource values such that the total weighted resource consumption is minimum, subject to meeting job deadlines. The algorithms are based on solving linear programming problems with two variables by geometric techniques.
---
paper_title: A polynomial-time approximation scheme for single-machine sequencing with delivery times and sequence-independent batch set-up times

paper_content:

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.
---
paper_title: Batching Identical Jobs

paper_content:

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.
---
paper_title: Batch scheduling with controllable setup and processing times to minimize total completion time

paper_content:

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.
---
paper_title: Scheduling with batching: two job types

paper_content:

In this paper we present an algorithm for the 2-weight batching problem: given n1 jobs with weight w1, and n2 jobs with weight w2, all having processing time p, and given a batch setup time Δ, find a sequence of batches of jobs such that the weighted sum of the n = n1 + N2 job completion times is minimized. The algorithm has running time O(n log n) when p and Δ are fixed; previously, the fastest known algorithm for this problem had running time O(n). Various properties of optimal solutions are exploited to reduce the problem to one of finding the minimum entry in a certain matrix. Since this matrix has some strong structural properties, its minimum entry can be found in time that is a sublinear function of the matrix size.
---
paper_title: Single machine batch scheduling with jointly compressible setup and processing times

paper_content:

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.
---
paper_title: Non-approximability of precedence-constrained sequencing to minimize setups

paper_content:

It is a basic scheduling problem to sequence a set of precedence-constrained tasks to minimize the number of setups, where the tasks are partitioned into classes that require the same setup. We prove a conjecture in (Ph.D. Thesis, School of ISyE, Georgia Institute of Technology, August 1986; Oper. Res. 39 (1991) 1012) that no polynomial-time algorithm for this problem has constant worst-case performance ratio unless P = NP. A very simple algorithm has performance ratio √n.
---
paper_title: Single machine batch scheduling with sequential job processing

paper_content:

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...
---
paper_title: A Stronger Complexity Result for the Single Machine Multi-Operation Jobs Scheduling Problem to Minimize the Number of Tardy Jobs

paper_content:

We consider the single machine multi-operation jobs scheduling problem to minimize the number of tardy jobs. Each job consists of several operations that belong to different families. In a schedule, each family of job operations may be processed in batches with each batch incurring a setup time. A job completes when all of its operations have been processed. The objective is to minimize the number of tardy jobs. In the literature, this problem has been proved to be strongly NP-hard for arbitrary due-dates. We show in this paper that the problem remains strongly NP-hard even when the due-dates are common and all jobs have the same processing time.
---
paper_title: Scheduling multi‐operation jobs on a single machine

paper_content:

We consider the problem of scheduling n multi‐operationjobs on a single machine. Eachjob comprises up to F operations that belong to different families.Changeovers of production from one family to another have associated set‐up times.A job completes when all of its operations have been processed. This type of problem arisesin the manufacture of food products. It combines the batching aspect of the well‐knownfamily scheduling models with an assembly element (where the job's operationsare assembled to make the final product).Our analysis covers three classic optimality criteria: the maximum lateness, theweighted number of late jobs, and the sum of job completion times. We show that the problemof minimizing the maximum lateness is equivalent to its counterpart without assembly.This enables us to derive extensions of known complexity results and to indicate appropriatealgorithms. The number of late jobs problem is shown to be binary NP‐hard when thereare two families, and unary NP‐hard when there are an arbitrary number of families,even when all set‐up times are identical. For a fixed number of families, we give adynamic programming algorithm to minimize the weighted number of late jobs, which requirespseudo‐polynomial running time. A similar algorithm solves the sum of completion timesproblem in polynomial time, under the additional assumption that the processing times ofoperations between families are agreeable. Copyright Kluwer Academic Publishers 1999
---
paper_title: Analytical models to predict the performance of a single-machine system under periodic and event-driven rescheduling strategies

paper_content:

This article presents initial results in the search for analytical models that can predict the performance of one-machine systems under periodic and event-driven rescheduling strategies in an environment where different job types arrive dynamically for processing and set-up must incur when production changes from one product type to another. The scheduling algorithm considered uses a first-in firstout dispatching rule to sequence jobs and it also groups jobs with similar types to save set-up time. The analytical models can estimate important performance measures like average flow time and machine utilization, which can then be used to determine optimal rescheduling parameters. Simulation experiments are used to show that the analytical models accurately predict the performance of the single machine under the scheduling algorithm proposed.
---
paper_title: Batch-processing scheduling with setup times

paper_content:

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.
---
paper_title: Single machine batch scheduling with resource dependent setup and processing times

paper_content:

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.
---
paper_title: Scheduling the production of two-component jobs on a single machine

paper_content:

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.
---
paper_title: Scheduling job families about an unrestricted common due date on a single machine

paper_content:

We consider the NP-hard problem of scheduling jobs on a single machine about an unrestricted due date to minimize total weighted earliness and tardiness cost. Jobs are grouped into families where jobs in the same family share a setup; a setup time is required between the processing of two jobs from different families. Each job has an earliness penalty rate and a tardiness penalty rate that are allowed to be arbitrary. These rates are assessed on a per-period basis when the completion time deviates from its due date. In this paper, we generalize properties from the literature that characterize the structure of an optimal schedule, present a lower bound, propose a branch and bound algorithm and a beam search procedure, and report results from a computational experiment. We find that optimal solutions can be quickly obtained for smaller problem instances. For large problems, we find high quality solutions within a few minutes of CPU time.
---
paper_title: Group Scheduling with Controllable Setup and Processing Times: Minimizing Total Weighted Completion Time

paper_content:

The following single machine scheduling problem is studied. A partition of a set of n jobs into g groups on the basis of group technology is given. The machine processes jobs of the same group contiguously, with a sequence independent setup time preceding the processing of each group. The setup times and the job processing times are controllable through the allocation of a continuously divisible or discrete resource to them. Each job uses the same amount of the resource. Each setup also uses the same amount of resource, which may be different from that for the jobs. Polynomial-time algorithms are constructed for variants of the problem of finding an optimal job sequence and resource values so as to minimize the total weighted job completion time, subject to given restrictions on resource consumption. The algorithms are based on a polynomial enumeration of the candidates for an optimal job sequence and solving the problem with a fixed job sequence by linear programming.
---
paper_title: Scheduling to minimize the maximum lateness with multiple product classes in batch processing

paper_content:

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.
---
paper_title: A heuristic approach to batching and scheduling a single machine to minimize setup costs

paper_content:

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.
---
paper_title: Scheduling a flowline manufacturing cell with sequence dependent family setup times

paper_content:

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.
---
paper_title: A case study in a two-stage hybrid flow shop with setup time and dedicated machines

paper_content:

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.
---
paper_title: Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups

paper_content:

This paper considers the problem of scheduling part families and jobs within each part family in a flowshop manufacturing cell with sequence dependent family setups times where it is desired to minimize the makespan while processing parts (jobs) in each family together. Two evolutionary algorithms-a Genetic Algorithm and a Memetic Algorithm with local search-are proposed and empirically evaluated as to their effectiveness in finding optimal permutation schedules. The proposed algorithms use a compact representation for the solution and a hierarchically structured population where the number of possible neighborhoods is limited by dividing the population into clusters. In comparison to a Multi-Start procedure, solutions obtained by the proposed evolutionary algorithms were very close to the lower bounds for all problem instances. Moreover, the comparison against the previous best algorithm, a heuristic named CMD, indicated a considerable performance improvement.
---
paper_title: An efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times

paper_content:

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.
---
paper_title: A Dynamic Heuristic for the Stochastic Unrelated Parallel Machine Scheduling Problem

paper_content:

This paper addresses the problem of batch scheduling in an unrelated parallel machine environment with sequence dependent setup times and an objective of minimizing the total weighted mean completion time. The jobs' processing times and setup times are stochastic for better depiction of the real world. This is a NP-hard problem and in this paper, new heuristics are developed and compared to existing ones using simulation. The results and analysis obtained from the computational experiments proved the superiority of the proposed algorithm PMWP over the other algorithms presented.
---
paper_title: An assembly scheduler for TFT LCD manufacturing

paper_content:

This paper presents development of a scheduling system for Thin Film Transistor Liquid Crystal Display (TFT LCD) assembly process. With given daily production plan that is rough-cut capacitated, the scheduler generates shift-based capacity feasible schedules at each assembly step. The scheduling problem is a parallel-machine scheduling problem with sequence dependent setups and some manufacturing environments, which make the problem considerably difficult. The scheduling objective is to minimize the mean flow time and maximize the production progressiveness. Two scheduling heuristics are proposed for each production step of assembly process. The first scheduling heuristic is applicable for the first three steps of assembly process, i.e. coating, rubbing, and attaching step, and for the later steps another similar heuristic is employed. We also propose a simple method for computing production requirements for each step where daily production demand is unknown. The proposed scheduling procedures are implemented in a real TFT LCD manufacturing line and their performances are investigated. The experimental results show that the proposed scheduler provides quite better schedules than the current practice employed in the line in terms of both mean flow time and fulfillment of production demands.
---
paper_title: Dynasearch for the earliness–tardiness scheduling problem with release dates and setup constraints

paper_content:

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.
---
paper_title: Exact algorithms for scheduling multiple families of jobs on parallel machines

paper_content:

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.
---
paper_title: Two-machine group scheduling problems in discrete parts manufacturing with sequence-dependent setups

paper_content:

This paper focuses on minimizing the total completion time in two-machine group scheduling problems with sequence-dependent setups that are typically found in discrete parts manufacturing. As the problem is characterized as strongly NP-hard, three search algorithms based on tabu search are developed for solving industry-size scheduling problems. Four different lower bounding mechanisms are developed to identify a lower bound for all problems attempted, and the largest of the four is aptly used in the evaluation of the percentage deviation of the search algorithms to assess their efficacy. The problem sizes are classified as small, medium and large, and to accommodate the variability that might exist in the sequence-dependent setup times on both machines, three different scenarios are considered. Such finer levels of classification have resulted in the generation of nine different categories of problem instances, thus facilitating the performance of a very detailed statistical experimental design to assess the efficacy and efficiency of the three search algorithms. The search algorithm based on long-term memory with maximal frequencies either recorded a statistically better makespan or one that is indifferent when compared with the other two with all three scenarios and problem sizes. Hence, it is recommended for solving the research problem. Under the three scenarios, the average percentage deviation for all sizes of problem instances solved has been remarkably low. In particular, a mathematical programming based lower bounding mechanism, which focuses on converting (reducing) the original sequence-dependent group scheduling problem with several jobs in each group to a sequence-dependent job scheduling problem, has served well in identifying a high quality lower bound for the original problem, making it possible to evaluate a lower average percentage deviation for the search algorithm. Also, a 16-17-fold reduction in average computation time for solving a large problem instance with the recommended search algorithm compared with identifying just the lower bound of (not solving) the same instance by the mathematical programming based mechanism speaks strongly in favor of the search algorithm for solving industry-size group scheduling problems. Scope and purpose: With an ever increasing demand for setting up manufacturing cells in the production of discrete parts to realize the benefits advocated in lean manufacturing systems, group scheduling has become a topic of research with significant industrial relevance. The problem addressed in this paper is motivated by the need for having to investigate such a problem in the presence of sequence-dependent setups in a two-machine environment to minimize the makespan, which to the best of the authors' knowledge is the first of its kind. Recognizing the complexity of the problem, three search algorithms based on tabu search have been developed to efficiently solve problem instances that belong to nine different categories, as a result of considering three different sizes, ranging from small, medium to large, and three different scenarios. In order to assess the efficacy of the search algorithms, four different lower bounding mechanisms have been developed and the largest of the four is aptly used to evaluate the percentage deviation in every problem instance attempted. The average percentage deviation of the solutions found by the search algorithms has been remarkably low. We view our contribution as that which looks into such detailed levels of investigation, emphasizing a blend of new theory and practice in the area of group scheduling.
---
paper_title: Unrelated parallel machine scheduling with setup times and a total weighted tardiness objective

paper_content:

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.
---
paper_title: Multi-objective scheduling of two-job families on a single machine

paper_content:

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.
---
paper_title: Minimizing sum of completion times on a single machine with sequence-dependent family setup times

paper_content:

This paper presents a branch-and-bound (B&B) algorithm for minimizing the sum of completion times in a single-machine scheduling setting with sequence-dependent family setup times. The main feature of the B&B algorithm is a new lower bounding scheme that is based on a network formulation of the problem. With extensive computational tests, we demonstrate that the B&B algorithm can solve problems with up to 60 jobs and 12 families, where setup and processing times are uniformly distributed in various combinations of the [1,50] and [1,100] ranges.
---
paper_title: Group technology in a hybrid flowshop environment: A case study

paper_content:

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.).
---
paper_title: Scheduling and lot streaming in flowshops with no-wait in process

paper_content:

Lot streaming involves splitting a production lot into a number of sublots, in order to allow the overlapping of successive operations, in multi-machine manufacturing systems. In no-wait flowshop scheduling, sublots are necessarily consistent, that is, they remain the same over all machines. The benefits of lot streaming include reductions in lead times and work-in-process, and increases in machine utilization rates. We study the problem of minimizing the makespan in no-wait flowshops producing multiple products with attached setup times, using lot streaming. Our study of the single product problem resolves an open question from the lot streaming literature. The intractable multiple product problem requires finding the optimal number of sublots, sublot sizes, and a product sequence for each machine. We develop a dynamic programming algorithm to generate all the nondominated schedule profiles for each product that are required to formulate the flowshop problem as a generalized traveling salesman problem. This problem is equivalent to a classical traveling salesman problem with a pseudopolynomial number of cities. We develop and computationally test an efficient heuristic for this problem. Our results indicate that solutions can quickly be found for flowshops with up to 10 machines and 50 products. Moreover, the solutions found by our heuristic provide a substantial improvement over previously published results.
---
paper_title: Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective

paper_content:

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.
---
paper_title: Equal processing and equal setup time cases of scheduling parallel machines with a single server

paper_content:

This paper considers the deterministic problem of scheduling two-operation non-preemptable jobs on two identical semi-automatic machines. A single server is available to carry out the first (or setup) operation. The second operation is executed automatically, without the server. The general problem of makespan minimization is NP-hard in the strong sense. Two special cases which arise in practice, the equal processing times and regular equal setup times problems turn out to be closely linked to the restricted set partitioning problem. This link is used to show that they are NP-hard in the ordinary sense, and to construct a tight lower bound and two highly effective O(n log n) heuristics.
---
paper_title: A divide and merge heuristic for the multiprocessor scheduling problem with sequence dependent setup times

paper_content:

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.
---
paper_title: List Scheduling in a Parallel Machine Environment with Precedence Constraints and Setup Times

paper_content:

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.
---
paper_title: Parallel machine scheduling with splitting jobs

paper_content:

Abstract To schedule n jobs on m parallel machines with the minimum total cost is the parallel machine scheduling (PMS) problem. Generally, there is a hypothesis: a job cannot be processed on two machines simultaneously if preemption is allowed. When the processing requirement of a job is considered as the demand of a product, jobs can be split arbitrarily to continuous sublots and processed independently on m machines. So, we can discuss PMS under a hypothesis: any part of a job can be processed on two different machines at the same time, and we call it PMS with splitting jobs. In this paper, we first present some simple cases which are polynomial solvable. Furthermore, a heuristic ML and its worst-case analysis are shown for P / split / C max with independent job setup times. The worst-case performance ratio of ML is within 7 4 −1/m (m⩾2) .
---
paper_title: Parallel machine scheduling with a common server

paper_content:

This paper considers the nonpreemptive scheduling of a given set of jobs on several identical, parallel machines. Each job must be processed on one of the machines. Prior to processing, a job must be loaded (setup) by a single server onto the relevant machine. The paper considers a number of classical scheduling objectives in this environment, under a variety of assumptions about setup and processing times. For each problem considered, the intention is to provide either a polynomial- or pseudo-polynomial-time algorithm, or a proof of binary or unary NP-completeness. The results provide a mapping of the computational complexity of these problems.
---
paper_title: Minimizing the sum of earliness/tardiness in multi-machine scheduling: a mixed integer programming approach

paper_content:

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.
---
paper_title: Parallel machine scheduling problems with a single server

paper_content:

In this paper, we consider the problem of scheduling jobs on parallel machines with setup times. The setup has to be performed by a single server. The objective is to minimize the schedule length (makespan), as well as the forced idle time. The makespan problem is known to be NP-hard even for the case of two identical parallel machines. This paper presents a pseudopolynomial algorithm for the case of two machines when all setup times are equal to one. We also show that the more general problem with an arbitrary number of machines is unary NP-hard and analyze some list scheduling heuristics for this problem. The problem of minimizing the forced idle time is known to be unary NP-hard for the case of two machines and arbitrary setup and processing times. We prove unary NP-hardness of this problem even for the case of constant setup times. Moreover, some polynomially solvable cases are given.
---
paper_title: Heuristic scheduling of parallel machines with sequence-dependent set-up times

paper_content:

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...
---
paper_title: MINIMIZING THE SUM OF JOB EARLINESS AND TARDINESS IN A MULTIMACHINE SYSTEM

paper_content:

We provide a heuristic algorithm for minimizing job earliness and tardiness cost in a multimachine scheduling problem. Our formulation explicitly separates machine setup times from processing times, assumes that setup times may depend on the job-to-job sequence, and assumes that processing times may depend on the job-machine combination. The new algorithm can easily provide approximate solutions to problems involving about 10 machines and 100 jobs when using a personal computer. The accuracy of the solutions was measured using a large variety of problem types taken from the literature. Relative accuracy was measured by comparing the new algorithm's results with those from other heuristics, and absolute accuracy was measured by comparing with results obtained using integer programming methods. The new algorithm was significantly more accurate than the other heuristics, and its average deviation was only about 10% when compared to the optimal solutions. In many cases the new algorithm yielded the optimal so...
---
paper_title: A heuristic algorithm for minimizing mean flow time with unit setups

paper_content:

Abstract In this note we consider the problem of scheduling a set of jobs on m identical parallel machines. For each job, a setup has to be done by a single server. The objective is to minimize the sum of the completion times in the case of unit setup times and arbitrary processing times. For this strongly NP-hard problem, we give a heuristic algorithm with an absolute error bounded by the product of the number of short jobs (with processing times less than m−1 ) and m−2 .
---
paper_title: Scheduling two parallel semiautomatic machines to minimize machine interference

paper_content:

We consider the problem of scheduling two parallel semiautomatic machines sharing the same server for setting up jobs with the objective of minimizing the machine idle time resulting from the unavailability of the server. The problem is shown to be strongly NP-hard and a reduction procedure is developed to transform it into a smaller one with all consecutive job completions alternating between the two machines. In the latter problem, regeneration points are identified for simplifying the idle time computations, leading to the development of an efficient beam search heuristic. Computational results indicate that the beam search performs very favourably when compared with local search on a wide variety of problems.
---
paper_title: Approximation algorithm for parallel machine scheduling with a common server

paper_content:

In this paper we study the scheduling of a given set of jobs on several identical parallel machines tended by a common server. Each job must be processed on one of the machines. Prior to processing, the server has to set up the relevant machine. The objective is to schedule the jobs so as to minimize the total weighted job completion times. We provide an approximation algorithm to tackle this intractable problem and analyze the worst-case performance of the algorithm for the general, as well as a special, case of the problem.
---
paper_title: Scheduling two parallel machines with a single server: the general case

paper_content:

This paper considers the problem of scheduling two-operation non-preemptable jobs on two identical semi-automatic machines. A single server is available to carry out the first (or setup) operation. The second operation is executed automatically, without the server. The general problem of makespan minimization is NP-hard in the strong sense. In earlier work, we showed that the equal total length problem is polynomial time and we also provided efficient and effective solutions for the special cases of equal setup and equal processing times. Most of the cases analyzed thus far have fallen into the category of regular problems. In this paper we build on this earlier work to deal with the general case. Various approaches will be considered. One may reduce the problem to a regular one by amalgamating jobs, or we may apply the earlier heuristics to (possibly regular) job clusters. Alternately we may apply a greedy heuristic, a metaheuristic such as a genetic algorithm or the well known Gilmore-Gomory algorithm to solve the general problem. We report on the performance of these various methods.
---
paper_title: Scheduling for parallel dedicated machines with a single server

paper_content:

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule isNP-hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP-hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore{Gomory traveling salesman problem and solve it in polynomial time. c 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304{328, 2000
---
paper_title: SOFT COMPUTING FOR SCHEDULING WITH BATCH SETUP TIMES AND EARLINESS-TARDINESS PENALTIES ON PARALLEL MACHINES

paper_content:

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.
---
paper_title: Unrelated parallel machine scheduling with setup times using simulated annealing

paper_content:

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.
---
paper_title: Batching decisions for assembly production systems

paper_content:

The two-stage assembly scheduling problem is a model for production processes that involve the assembly of final or intermediate products from basic components. In our model, there are m machines at the first stage that work in parallel, and each produces a component of a job. When all components of a job are ready, an assembly machine at the second stage completes the job by assembling the components. We study problems with the objective of minimizing the makespan, under two different types of batching that occur in some manufacturing environments. For one type, the time to process a batch on a machine is equal to the maximum of the processing times of its operations. For the other type, the batch processing time is defined as the sum of the processing times of its operations, and a setup time is required on a machine before each batch. For both models, we assume a batch availability policy, i.e., the completion times of the operations in a batch are defined to be equal to the batch completion time. We provide a fairly comprehensive complexity classification of the problems under the first type of batching, and we present a heuristic and its worst-case analysis under the second type of batching.
---
paper_title: Scheduling Batches with Sequential Job Processing for Two-Machine Flow and Open Shops

paper_content:

In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these asconsistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested.
---
paper_title: Makespan minimization in the two-machine flowshop batch scheduling problem

paper_content:

In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part-types are to be produced in a flexible manufacturing cell organized into a two-stage production line. The jobs are processed in batches on the first machine, and the completion time of a job is defined as the completion time of the batch containing it. When processing of all jobs in a batch is completed on the first machine, the whole batch of jobs is transferred intact to the second machine. A constant setup time is incurred whenever a batch is formed on any machine. The tradeoff between the setup times and batch processing times gives rise to the batch composition decision. The problem is to find the optimal batch composition and the optimal schedule of the batches so that the makespan is minimized. The problem is shown to be strongly NP-hard. We identify some special cases by introducing their corresponding solution methods. Heuristic algorithms are also proposed to derive approximate solutions. We conduct computational experiments to study the effectiveness of the proposed heuristics. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 128–144, 2000
---
paper_title: Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints

paper_content:

This research deals with scheduling jobs on unrelated parallel machines with auxiliary equipment constraints. Each job has a due date and requires a single operation. A setup for dies is incurred if there is a switch from processing one type of job to another type. For a die type, the number of dies is limited. Due to the attributes of the machines and the fitness of dies to each, the processing time for a job depends on the machine on which the job is processed, each job being restricted to processing on certain machines. In this paper, an effective heuristic based on threshold-accepting methods, tabu lists, and improvement procedures is proposed to minimize total tardiness. An extensive experiment is conducted to evaluate the computational characteristics of the proposed heuristic. Computational experiences demonstrate that the proposed heuristic is capable of obtaining optimal solutions for small-sized problems, and significantly outperforms an ATCS procedure and a simulated annealing method for problems in larger sizes.
---
paper_title: Parallel Machine Scheduling by Family Batching with Sequence-independent Set-up Times

paper_content:

This paper presents a new approach for transforming MRP orders, planned periodically, e.g. on a weekly base, into a detailed schedule of jobs. In this model for a parallel machine environment, the jobs are partitioned into families and a family specific set-up time is required at the start of each period and of each batch, where a batch is a maximal set of jobs in the same family, that are processed consecutively. An integer program is formulated for both the problem of minimising the number of overloaded periods and the problem of minimising the total overtime. These programs generate benchmark results for the heuristic approach. A heuristic model is developed that constructs a schedule in which overloaded periods are relieved and set-up time is saved. In this approach, the job sequence is constructed by repeatedly solving a knapsack problem for each machine. The weights used in this knapsack problem relate to the preferred priorities of the jobs not yet scheduled and determine the quality of the final sequence. The different features of the heuristic model are compared using a large set of test problems. The results show that the quality of the final schedule depends on an appropriate choice of the weights.
---
paper_title: Two-Machine Flowshop Batching and Scheduling

paper_content:

We consider in this paper a two-machine flowshop scheduling problem in which the first machine processes jobs individually while the second machine processes jobs in batches. The forming of each batch on the second machine incurs a constant setup time. The objective is to minimize the makespan. This problem was previously shown to be NP-hard in the ordinary sense. In this paper, we first present a strong NP-hardness result of the problem. We also identify a polynomially solvable case with either anticipatory or non-anticipatory setups. We then establish a property that an optimal solution for the special case is a lower bound for the general problem. To obtain near-optimal solutions for the general problem, we devise some heuristics. The lower bound is used to evaluate the quality of the heuristic solutions. Results of computational experiments reveal that the heuristics produce solutions with small error ratios. They also suggest that the lower bound is close to the optimal solution.
---
paper_title: Batch scheduling in the no-wait two-machine flowshop to minimize the makespan

paper_content:

Abstract We consider a scheduling problem where a set of jobs are simultaneously available for processing in a no-wait two-machine flowshop. The objective is to minimize the makespan, i.e. the maximum completion time of the jobs. The operations of all jobs are processed on both machines in batches. A constant setup time is incurred whenever a batch is formed on the machines. The processing time of a batch is defined as the setup time plus the sum of all processing times of the jobs it contains. The completion time of a job is defined as the time at which the batch containing it is completely processed on machine two. The no-wait scheduling problem in the two-machine flowshop without batching is known as polynomially solvable. We show that several restricted versions of the problem under study in this paper are strongly NP -hard, which imply that the general problem is also strongly NP -hard. We then establish some interesting properties and exploit them to design solution methods for two special cases. Scope and purpose In this paper, we consider scheduling a set of jobs in a two-machine no-wait flowshop, which is a typical manufacturing setup for steel and plastic production. The jobs are sequentially processed on the machines in batches. A constant setup time is incurred whenever a batch is formed on any of the machines. Our goal is to finish all jobs in the earliest possible time. We first give NP -hardness proofs for three special cases. These results suggest that it is very unlikely to devise an efficient method to find an optimal schedule for the problem under study. We also design solution procedures for two further restricted cases, in which the jobs share some specific characteristics. This paper initiates research into scheduling with batching in the no-wait flowshop environment.
---
paper_title: Minimizing flow time in a flow-line manufacturing cell with family setup times

paper_content:

This paper considers the problem of scheduling part families and jobs within each part family in a flowline manufacturing cell with independent family setup times where parts (jobs) in each family are processed together. The objective is to minimize total flow time. A branch-and-bound algorithm capable of solving moderate sized problems is developed. Several heuristic algorithms are proposed and empirically evaluated as to their effectiveness and efficiency in finding optimal permutation schedules. These results show that several heuristic algorithms generate solutions that are better than those generated by an existing genetic algorithm.
---
paper_title: Dynamic programming algorithms for scheduling parallel machines with family setup times

paper_content:

Abstract We address the problem of scheduling jobs with family setup times on identical parallel machines to minimize total weighted flowtime. We present two dynamic programming algorithms — a backward algorithm and a forward algorithm — and we identify characteristics of problems where each algorithm is best suited. We also derive two properties that improve the computational efficiency of the algorithms. Scope and purpose While most production schedulers must balance conflicting goals of high system efficiency and timely completion of individual jobs, consideration of this conflict is underdeveloped in the scheduling literature. This paper examines a model that incorporates a fundamental cause of the efficiency/timeliness conflict in practice. We propose solution methodologies and properties of an optimal solution for the purpose of exposing insights that may ultimately be useful in research on more complex models.
---
paper_title: Batching in a two-stage flowshop with dedicated machines in the second stage

paper_content:

The problem of batching and scheduling n identical jobs of F, F ≥ 2, part types in a shop made up of F+1 machines is studied. The processing of each job comprises two stages. The first stage is undertaken on the machine common to all jobs and the second stage is undertaken on the machine specific to a particular part type. Setup times are necessary at the first stage to switch processing from a job of one part type to a job of another part type. Jobs of the same part type processed contiguously at the first stage form a batch. The objective is to find a batch schedule minimizing makespan. We show that this problem is equivalent to a special case of a single machine family scheduling problem to minimize maximum lateness and therefore it can be solved in O(n F ) time by a known algorithm. Furthermore, for the case where F = 2, we present an iterative exact algorithm with O(k 0log L) running time, where k 0 is the maximum number of batches in a schedule created in any iteration of the algorithm and L is the ...
---
paper_title: Lot splitting to minimize average flow-time in a two-machine flow-shop

paper_content:

Lot splitting is a technique for accelerating the flow of work by splitting job lots into sublots, In this paper we investigate the lot splitting scheduling problem in a two-machine flow-shop environment with detached setups and with batch availability. The performance measure considered is the average flow-time which is indicative of the increasingly important manufacturing lead-time. Our contribution is both theoretic and practical for the case of general (not necessarily equal) sublots. We identify properties of the optimal solution and develop a solution procedure to solve the problem. We then present a computational study which indicates that our solution technique is very efficient.
---
paper_title: A comparison of heuristic algorithms for flow shop scheduling problems with setup times and limited batch size

paper_content:

In this paper, we propose different heuristic algorithms for flow shop scheduling problems, where the jobs are partitioned into groups or families. Jobs of the same group can be processed together in a batch but the maximal number of jobs in a batch is limited. A setup is necessary before starting the processing of a batch, where the setup time depends on the group of the jobs. In this paper, we consider the case when the processing time of a batch is given by the maximum of the processing times of the operations contained in the batch. As objective function we consider the makespan as well as the weighted sum of completion times of the jobs. For these problems, we propose and compare various constructive and iterative algorithms. We derive suitable neighbourhood structures for such problems with batch setup times and describe iterative algorithms that are based on different types of local search algorithms. Except for standard metaheuristics, we also apply multilevel procedures which use different neighbourhoods within the search. The algorithms developed have been tested in detail on a large collection of problems with up to 120 jobs.
---
paper_title: Scheduling parallel machines to minimize weighted flowtime with family set-up times

paper_content:

We describe and evaluate several branch-and-bound algorithms for an identical parallel machine scheduling problem with family set-up times and an objective of minimizing total weighted flowtime. The algorithms differ by choice of lower bound method. Computational results suggest conditions favourable to a particular algorithm as well as the range of problem sizes that can be optimally solved in reasonable CPU time.
---
paper_title: Scheduling Grouped Jobs on Parallel Machines with Setups

paper_content:

This paper presents a job scheduling model of M identical machines in parallel. The model assumes that a set-up time is incurred when a machine changes from processing one type of parts to a different type of parts. And the scheduling objective is to minimize the sum of total flow time. We establish a heuristic and a tight lower bound (LB) on the optimal total flow time. The solution is analyzed by computational study. The comparisons of LB with heuristic and optimal solutions of small instances show that the solution quality of our heuristic is acceptable, and the heuristic has potential to solve larger practical problems.
---
paper_title: Two-machine flowshop group scheduling problem

paper_content:

Abstract This paper considers a two-machine flowshop group scheduling problem. The jobs are classified into groups and the jobs in the same group must be processed in succession. Each group requires a set up time and removal time on both machines. A transportation time is required for moving the jobs from machine 1 to machine 2. The objective is to minimize the maximum completion time (makespan). A polynomial time algorithm is proposed to solve the problem. This generalizes the algorithms proposed by Baker and others. Scope and purpose Recently, an important class of scheduling problem is characterized by a group scheduling constraint where the jobs are classified into groups by the same operation requirements or characters. Each group requires a setup time and removal time on both machines. That is, each machine needs a time to set up or to remove the tools, jigs and fixtures when the group starts processing or completes processing. A transportation time is required to move the jobs between the machines. The objective is to find a sequence of groups and jobs in each group such that the maximum completion time (makespan) is minimized. Baker provided an optimal algorithm for this problem in the case of two-machine flowshop group scheduling without considering the removal and transportation times. But, in some manufacturing environments, it is required to consider the group removal time and job transportation time. The main contribution of this paper is to develop a polynomial time algorithm, which generalizes the algorithms proposed by Baker and others.
---
paper_title: Exact algorithms for scheduling multiple families of jobs on parallel machines

paper_content:

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.
---
paper_title: A heuristic approach for tow-machine no-wait flowshop scheduling with due dates and class setups

paper_content:

This paper studies the two-machine flowshop scheduling problem with class setups in a no-wait processing environment to minimize the maximum lateness. The jobs are divided into job classes and a setup is required at the initial processing of a job or between the processing of jobs of different classes. In a no-wait environment, a job must be processed from start to finish without interruptions on a machine or between the machines. A batch is a maximal subset of consecutively processed jobs of the same class. Several properties concerning the beneficial merging of batches and some dominance rules that improve the objective function are derived. Since the problem is NP-hard, a heuristic is proposed and evaluated computationally. The numerical results demonstrate that the heuristic can produce near-optimal solutions quickly for realistic-sized problems.
---
paper_title: Fabrication and assembly scheduling in a two-machine flowshop

paper_content:

This paper considers a fabrication scheduling problem to minimize the makespan in a two-machine flowshop. Each job has a unique component and a common component to be processed on the first machine. On machine 1, the common components of the jobs are grouped into batches for processing with a setup cost incurred whenever a batch is formed. A job is ready for its assembly operation on the second machine if both its unique and common components are finished on machine 1. The problems with batch availability and item availability are known as NP-hard. In this paper, we give proofs for the strong NP-hardness of the two problems. The results suggest that it is very unlikely to develop polynomial- or pseudo-polynomial-time algorithm for finding exact solutions for the two problems.
---
paper_title: Scheduling non-similar groups on a flow line: multiple group setups

paper_content:

Abstract This research addresses lead-time reduction and makespan minimization for cut and sew operations of upholstered furniture manufacturing through efficient scheduling. Jobs are grouped based on different characteristics at each operation of this two stage flow line. There are identical parallel machines at each stage and jobs proceed individually from the 1st stage to the 2nd. A heuristic for the case of multiple setups per group at the 2nd stage is developed, compared to a single setup per group at each stage, and integrated into a genetic algorithm. Results demonstrate that the heuristic effectively adds minimal setups to a single setup schedule while significantly improving schedule makespan.
---
paper_title: Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs

paper_content:

Abstract There is a set of jobs available to process in batches on a set of identical parallel machines. A sequence-independent setup time is incurred whenever a batch is formed on any machine. The jobs in the same batch are continuously processed after the setup. The processing length of a batch is the sum of the setup time and the processing times of the jobs it contains. Under the batch availability constraint, the completion time of a job is defined as the time when the batch it belongs to is totally completed. With each job, a due date is specified for its completion. In this paper, we first consider the problem to schedule as well as group the jobs so that the maximum lateness is minimized. The second problem is to minimize the number of tardy jobs. We first design dynamic programming algorithms for finding optimal solutions to the two problems. Then, we design several heuristics and conduct computational experiments to study their relative performance.
---
paper_title: Two-machine flowshop scheduling with job class setups to minimize total flowtime

paper_content:

This paper studies the two-machine flowshop scheduling problem with job class setups to minimize the total flowtime. The jobs are classified into classes, and a setup is required on a machine if it switches processing of jobs from one class to another class, but no setup is required if the jobs are from the same class. For some special cases, we derive a number of properties of the optimal solution, based on which we design heuristics and branch-and-bound algorithms to solve these problems. Computational results show that these algorithms are effective in yielding near-optimal or optimal solutions to the tested problems.
---
paper_title: Flow-shop batch scheduling with identical processing-time jobs

paper_content:

In many practical situations of production scheduling, it is either necessary or recommended to group a large number of jobs into a relatively small number of batches. A decision needs to be made regarding both the batching (i.e., determining the number and the size of the batches) and the sequencing (of batches and of jobs within batches). A setup cost is incurred whenever a batch begins processing on a given machine. This paper focuses on batch scheduling of identical processing-time jobs, and machine- and sequence-independent setup times on an m-machine flow-shop. The objective is to find an allocation to batches and their schedule in order to minimize flow-time. We introduce a surprising and nonintuitive solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004
---
paper_title: Scheduling the production of two-component jobs on a single machine

paper_content:

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.
---
paper_title: Batch Scheduling in a Two Machine Flow Shop with Limited Buffer and Sequence Independent Setup Times

paper_content:

Abstract The problem of makespan minimization in a flow shop with two-machines when the input buffer of the second machine can only host a limited number c of parts is known to be NP-hard for any c >0 and c ⩽ n , where n is the number of jobs. In this paper we analyze this problem in the context of batch scheduling, i.e. when identical parts must be processed consecutively. In particular we study the case in which each batch requires sequence independent setup times and removal times. We then show that, if the size of the i th batch is larger than a value b i ∗ , then the makespan minimization problem can be formulated as a special case of TSP and solved in polynomial time. The cost structure of this TSP can be reduced to the one defined for the two-machine no-wait flow shop. Hence, we give a closed form expression for b i ∗ . Then, we prove that when the same algorithm is applied to batch sizes smaller than b i ∗ , the error goes to zero as the batch sizes approach the values b i ∗ .
---
paper_title: Multi-objective lot splitting for a single product m-machine flowshop line

paper_content:

In this paper, the mean flowtime and the makespan objectives are simultaneously investigated in a single product, m-machine, flowshop system. For this purpose, an efficiency frontier approach is applied and an optimal algorithm for generating all efficient solutions is developed. A comprehensive computational experiment is performed for analyzing the tradeoff between the two objectives and evaluating the proposed algorithm performance. The most-balanced-solution, MinMax, is defined and recommended as a desirable alternative for either the flowtime or the makespan optimal solutions. Results show that when the system is optimized for either the mean flowtime or the makespan, a significant loss in the nonoptimized objective value is observed. On the other hand, adopting the MinMax solution obtains a close to optimal solution in both objectives.
---
paper_title: Soft computing for parallel scheduling with setup times

paper_content:

A model of scheduling grouped jobs on identical parallel machines is discussed. The model assumes that a set-up time is incurred when a machine changes from processing one type of parts to a different type of parts, and the objective is to minimize the total flow time. The algorithm of 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 soft computing algorithm has potential for practical applications in larger scale production systems.
---
paper_title: Heuristic methods for the identical parallel machine flowtime problem with set-up times

paper_content:

We consider the scheduling of N jobs divided into G families for processing on M identical parallel machines. No set-up is necessary between jobs belonging to the same family. A set-up must be scheduled when switching from the processing of family i jobs to those of another family j, i ≠ j, the duration of this set-up being the sequence-independent set-up time sj for family j. We propose heuristics for this problem and computationally evaluate the performance of the heuristics relative to lower bounds and solutions obtained using an exact algorithm.
---
paper_title: Scheduling jobs on parallel machines with sequence-dependent family set-up times

paper_content:

This paper proposes an efficient heuristic to minimise the total weighted tardiness of a set of tasks with known processing times, due dates, weights and family types for parallel machines. A three-phase heuristic is presented to minimise total weighted tardiness. In the first phase, jobs are listed by the earliest due date and then divided into small job-sets according to a decision parameter. In the second phase, jobs are grouped by the due date within applicable families using apparent tardiness cost with set-up (ATCS), and the sequence of jobs within families is improved through the use of the tabu search method. In the third phase, jobs are allocated to machines using a threshold value and a look-ahead parameter. The comprehensive simulation results show that the proposed heuristic performs better than the ATCS and rolling horizon procedure at a significantly reduced total weighted tardiness.
---
paper_title: Multi-family scheduling in a two-machine reentrant flow shop with setups

paper_content:

Abstract This paper considers a two-machine multi-family scheduling problem with reentrant production flows. The problem consists of two machines, M1 and M2, and each job has the processing route (M1, M2, M1, M2). There are identical jobs in the same family and the jobs in the same family are processed in succession. Each machine needs a setup time before the first job in a family is processed. The objective is to minimize the maximum completion time. Examples of such a problem occur in the bridge construction, semiconductor industry and job processing on numerical controlled machines, where they usually require that the jobs are reprocessed once and there are identical jobs in the same family. This problem is shown to be NP-hard. A branch-and-bound algorithm is proposed, and computational experiments are provided.
---
paper_title: Production sequencing problem with re-entrant work flows and sequence dependent setup times

paper_content:

This paper addresses a shop scheduling problem where a set of n jobs needs to be scheduled on two machines for the side frame press shop in a truck manufacturing company. A most unusual aspect of the problem is that the setup times required for a job in the first machine depend not on the immediately preceding job but on the job which is two steps prior to it. Redefining the job elements, the problem is formulated into a general two machine flow shop problem which can be solved by dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance conditions and the decisiondelay scheme. Since the computational requirements of dynamic programming are impracticably demanding for large-sized problems, a genetic algorithm is developed and its performance is examined through a comparative study.
---
paper_title: Heuristic for scheduling in a two-machine bicriteria dynamic flowshop with setup and processing times separated

paper_content:

This paper addresses the two-machine bicriteria dynamic flowshop problem where setup time of a job is separated from its processing time and is sequenced independently. The performance considered is the simultaneous minimization of total flowtime and makespan, which is more effective in reducing the total scheduling cost compared to the single objective. A frozen-event procedure is first proposed to transform a dynamic scheduling problem into a static one. To solve the transformed static scheduling problem, an integer programming model with N 2 + 5N variables and 7N constraints is formulated. Because the problem is known to be NP-complete, a heuristic algorithm with the complexity of O (N 3) is provided. A decision index is developed as the basis for the heuristic. Experimental results show that the proposed heuristic algorithm is effective and efficient. The average solution quality of the heuristic algorithm is above 99%. A 15-job case requires only 0.0235 s, on average, to obtain a near or even optimal...
---
paper_title: Scheduling flowshops with finite buffers and sequence-dependent setup times

paper_content:

In this paper we explore flowshop scheduling problems containing both sequence-dependent setup times and finite buffers. To the best of our knowledge, problems containing both of these complexities have not been addressed previously in the literature. The problem is clearly NP-hard and therefore we only consider heuristic solution methods. We propose a tabu search based solution procedure. Computational results demonstrate the effectiveness of this approach relative to the other methods discussed.
---
paper_title: A heuristic for scheduling to minimize the sum of weighted flowtime of jobs in a flowshop with sequence-dependent setup times of jobs

paper_content:

The problem of scheduling in a static flowshop with sequence-dependent setup times of jobs (FSDS) is considered in this paper. A new heuristic to minimize the sum of weighted flowtime of jobs in a FSDS is proposed. An improvement scheme is supplemented to enhance the quality of the heuristic solution. An extensive computational performance analysis has shown that the proposed heuristic is computationally faster and more effective in yielding solutions of better quality than the existing heuristic. An interesting observation is that even though the proposed heuristic aims to minimize the sum of weighted flowtime of jobs (just like the existing heuristic), it fares much better than the existing heuristic in minimizing the maximum weighted flowtime of a job too.
---
paper_title: Decomposition methods for reentrant flow shops with sequence-dependent setup times

paper_content:

We consider the problem of scheduling a reentrant flow shop with sequence-dependent setup times to minimize maximum lateness. We develop a series of decomposition methods (DMs) exploring the importance of components such as subproblem solution method, bottleneck identification and reoptimization method on the solution time/quality tradeoff. Based on these results, we propose an enhanced DM which gives promising results for these difficult scheduling problems. Our results also yield interesting insights into the strengths and limitations of DMs. Copyright © 2000 John Wiley & Sons, Ltd.
---
paper_title: Minimizing mean flowtime in a two-machine flowshop with sequence-independent setup times

paper_content:

This paper addresses the two-machine flowshop problem to minimize mean flowtime where setup times are separated and sequence independent. Optimal solutions are obtained for two special cases. For the general case, two dominance relations are established and their effectiveness in a branch-and-bound algorithm is evaluated. It is shown that problems up to 35 jobs can be solved optimally in a reasonable time. Moreover, for the general case, three heuristic algorithms are proposed to find an approximate solution for larger problems, and they are empirically evaluated to assess their effectiveness in finding the optimal solution. Computational results show that one of the heuristic algorithms has an overall average error of 0.7% from the optimal value and that the error is independent of the number of jobs. ::: ::: ::: Scope and purpose ::: ::: A flowshop scheduling problem involves scheduling a number of jobs on a number of machines in order to optimize a given criterion. The majority of research assumes that setup times are negligible or can be combined with the processing times. However, the latter assumption is invalid in the case of sequence-dependent setup times and may lead to more idle time on some of the machines in the case of sequence-independent setup times. This illustrates the importance of considering setup times as separate from processing times. In the literature, the separate setup times problem has been mainly addressed with the criterion of makespan. Minimizing makespan is important in situations where a simultaneously received batch of jobs is required to be completed as soon as possible. For example, a multi-item order submitted by a single customer that needs to be delivered at the minimal possible time. However, there are other real life situations in which each completed job is needed as soon as it is processed. In such situations, one is interested in minimizing the mean or sum of flow (completion) times of all jobs rather than minimizing makespan. This objective is particularly important in real life situations in which reducing inventory or holding cost is of primary concern. This paper addresses a two-machine flowshop scheduling problem with separate setup times in order to minimize mean flowtime.
---
paper_title: Two models for a family of flowshop sequencing problems

paper_content:

Abstract This paper presents two mixed-integer linear programming (MILP) models (referred to as WST and SGST in the paper) for a family of four different M-machine, N -job flowshop sequencing problems. Each model may be used to solve the regular, no intermediate queues (NIQ), sequence-dependent setup times (SDST), and SDST/NIQ flowshop problems. The optimal job sequence, based on minimizing makespan, is achieved by a positional assignment approach in the WST model, and by pairs of disjunctive (either–or) constraints in the SGST model. A 12-cell experimental design was used to compare the solution times of the two models for each of the four flowshop problems. The WST model used significantly less computer time than the SGST model for all problem sizes in the regular, NIQ, and SDST flowshop problems. Both models were competitive in the SDST/NIQ flowshop for N ⩽7, but the WST model proved significantly better for N ⩾8.
---
paper_title: One-operator-two-machine flowshop scheduling with setup and dismounting times

paper_content:

Abstract In this paper we study the problem of scheduling n jobs in a one-operator–two-machine flowshop. In such a flowshop, before a machine begins processing a job, the operator has to set up the machine, and then the machine can process the job on its own. After a machine finishes processing a job, the operator needs to perform a dismounting operation before setting up the machine for another job. The setup and dismounting operations are either separable or nonseparable. The objective is to minimize the makespan. Confining our study to cyclic-movement schedules which require the operator to move between the two machines according to some cyclic pattern, we show that both the cyclic-movement separable and nonseparable setup and dismounting problems are NP-complete in the strong sense. We then propose some heuristics and analyze their worst-case error bounds. Scope and purpose The one-worker–multiple-machine (OWMM) concept is widely applied in just-in-time (JIT) manufacturing systems. In an OWMM system, a worker tends several machines simultaneously where each of the machines performs a different operation, and the different machines make up a flow line. In this paper, we study a scheduling problem in the one-operator–two-machine system where the operator moves between two machines according to some cyclic pattern, and performs the setup and dismounting operations on both machines. Both separable and nonseparable setup and dismounting problems are considered.
---
paper_title: Flowshop Scheduling of Robotic Cells with Job-dependent Transportation and Set-up Effects

paper_content:

A flexible manufacturing cell consisting of two machining centres, several automated storage/retrieval stations, and a mobile transporting robot is considered. The problem is to schedule jobs on machines so as to minimize the makespan, with the effects of transportation and set-ups to be taken into account. The problem is studied with the aid of a graph model, and an exact algorithm of cubic complexity is derived based on the Gilmore–Gomory algorithm for the travelling salesman problem.
---
paper_title: Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics

paper_content:

Abstract This paper deals with the permutation flowshop scheduling problem in which there are sequence dependent setup times on each machine, commonly known as the SDST flowshop. The optimisation criteria considered is the minimisation of the makespan or C max . Genetic algorithms have been successfully applied to regular flowshops before, and the objective of this paper is to assess their effectiveness in a more realistic and complex environment. We present two advanced genetic algorithms as well as several adaptations of existing advanced metaheuristics that have shown superior performance when applied to regular flowshops. We show a calibration of the genetic algorithm's parameters and operators by means of a Design of Experiments (DOE) approach. For evaluating the proposed algorithms, we have coded several, if not all, known SDST flowshop specific algorithms. All methods are tested against an augmented benchmark based on the instances of Taillard. The results show a clear superiority of the algorithms proposed, especially for the genetic algorithms, regardless of instance type and size.
---
paper_title: The Flow Shop Scheduling Polyhedron with Setup Times

paper_content:

This paper addresses the problem of improving the polyhedral representation of a certain class of machine scheduling problems. Despite the poor polyhedral representation of many such problems in general, it is shown that notably tighter linear programming representations can be obtained for many important models. In particular, we study the polyhedral structure of two different mixed-integer programming formulations of the flow shop scheduling problem with sequence-dependent setup times, denoted by SDST flow shop. The first is related to the asymmetric traveling salesman problem (ATSP) polytope. The second is less common and is derived from a model proposed by Srikar and Ghosh based on the linear ordering problem (LOP) polytope. The main contribution of this work is the proof that any facet-defining inequality (facet) of either of these polytopes (ATSP and LOP) induces a facet for the corresponding SDST flow shop polyhedron. The immediate benefit of this result is that all developments to date on facets and valid inequalities for both the ATSP and the LOP can be applied directly to the machine scheduling polytope. In addition, valid mixed-integer inequalities based on variable upper-bound flow inequalities for either model are developed as well. The derived cuts are evaluated within a branch-and-cut framework.
---
paper_title: Scheduling to minimize the sum of weighted flowtime and weighted tardiness of jobs in a flowshop with sequence-dependent setup times

paper_content:

Abstract Efficient heuristics for scheduling jobs in a static flowshop with sequence-dependent setup times of jobs are presented in this paper. The objective is to minimize the sum of weighted flowtime and weighted tardiness of jobs. Two heuristic preference relations are used to construct a good heuristic permutation sequence of jobs. Thereafter, an improvement scheme is implemented, once and twice, on the heuristic sequence to enhance the quality of the solution. An existing heuristic, a random search procedure and a greedy local search are used as benchmark methods for relatively evaluating the proposed heuristics. An extensive performance analysis has shown that the proposed heuristics are computationally faster and more effective in yielding solutions of better quality than the benchmark procedures.
---
paper_title: A new dynamic programming formulation of (n x m) flowshop sequencing problems with due dates

paper_content:

A dynamic programming formulation is presented for determining an optimal solution to a problem where n jobs are to be sequenced in a multi-stage production environment. An application of a developed formulation to a plastic pipe manufacturing factory is also presented. Conditions are such that the job sequence is the same in all stages, each job requires setups at each stage and setup times are sequence dependent. An optimal solution is such that the minimum total tardiness is achieved. A listing of the developed computer program is also provided.
---
paper_title: Scheduling problem in a two-machine flow line with the N-step prior-job-dependent set-up times

paper_content:

The purpose of this study is to develop effective scheduling methodologies for the shop scheduling problem of a flow line. The flow line consists of two machines where only the second machine has separable, external, and sequence-dependent set-up times. The length of set-up times required for a job depends not on the immediately preceding job but on the job which is n steps prior to it. The problem is solved by a dynamic programming with the objective of minimizing the make span. An optimal schedule is found utilizing the sequence dominance condition. Since the computational requirements of the dynamic programming are impracticably demanding for large-sized problems, a genetic algorithm is developed and its performance is examined through a comparative study.
---
paper_title: Production sequencing problem with reentrant work flows and sequence dependent setup times

paper_content:

This paper addresses a shop scheduling problem for the side frame press shop in a truck manufacturing company. In the problem, a set of n jobs to be scheduled on two machines. All the jobs require processing by the first machine more than once in their operation sequences with reentrant work flows. An unusual aspect of the problem is that the setup times required for a job in the first machine depend not on the immediately preceding job but on the job which is two steps prior to it. Redefining the job elements, the problem is formulated into a general two machine flow shop problem which has a set of job-element precedence constraints. The problem is solved with a modified dynamic programming with the objective of the minimum makespan. An optimal schedule is found utilizing the sequence dominance condition and a decision-delay scheme. A numerical example is presented for the illustration purpose.
---
paper_title: A penalty-based heuristic algorithm for the permutation flowshop scheduling problem with sequence-dependent set-up times

paper_content:

This paper considers the permutation flowshop scheduling problem with sequence-dependent set-up times and develops a penalty-based heuristic algorithm to find an approximately minimum makespan schedule. The proposed algorithm determines the penalty in time associated with a particular sequence and selects the sequence with the minimum time penalty as the best heuristic solution. Computational results comparing the effectiveness and efficiency of the proposed penalty-based heuristic algorithm with an existing savings index heuristic algorithm are reported and discussed.
---
paper_title: Complexity Results for Flow-Shop Problems with a Single Server

paper_content:

Flow-shop problems with a single server are generalizations of classical flow-shop problems. Immediately before processing, each operation must be loaded onto the corresponding machine, which takes a certain setup time. These setup times are assumed to be separable from the processing times, i.e. a setup on a subsequent machine may be performed while the job is still processed on the preceding machine. All setups have to be done by a single server which can perform at most one setup at a time. New complexity results are derived for special cases.
---
paper_title: Scheduling for parallel dedicated machines with a single server

paper_content:

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule isNP-hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP-hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore{Gomory traveling salesman problem and solve it in polynomial time. c 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304{328, 2000
---
paper_title: An Enhanced TSP-Based Heuristic for Makespan Minimization In a Flow Shop with Setup Times

paper_content:

This paper presents an enhanced heuristic for minimizing the makespan of the flow shop scheduling problem with sequence-dependent setup times. The procedure transforms an instance of the problem into an instance of the traveling salesman problem by introducing a cost function that penalizes for both large setup times and bad fitness of schedule. This hybrid cost function is an improvement over earlier approaches that penalized for setup times only, ignoring the flow shop aspect of the problem. To establish good parameter values, each component of the heuristic was evaluated computationally over a wide range of problem instances. In the testing stage, an experimental comparison with a greedy randomized adaptive search procedure revealed the conditions and data attributes where the proposed procedure works best.
---
paper_title: A heuristic for scheduling two-machine no-wait flow shops with anticipatory setups

paper_content:

We consider a problem of scheduling jobs in two-machine no-wait flow shops for which the objective is to minimize the makespan. Each job, upon completion of its processing on the first machine, must be transferred immediately to the second machine due to a no-wait in process constraint. Every job requires a setup time on each machine before it is processed. The setup on the second machine is anticipatory, since it can be performed in advance of an arriving job, and consists of two parts. During the first part of the setup, the job should not be present in the machine, while the second part of setup can be done in the presence or absence of the job. A heuristic algorithm is proposed, and its worst-case performance ratio of 4/3 is established.
---
paper_title: Two-Machine No-Wait Flowshop Scheduling Problem to Minimize Maximum Lateness with Separate Setup and Removal Times

paper_content:

We address the two-machine no-wait flowshop scheduling problem to minimize maximum lateness where setup and removal times are treated as separate from processing time. We obtain optimal solutions for special cases. Moreover, we propose a branch-and-bound algorithm for the generic case. We conduct extensive experimentations to evaluate the performance of the proposed branch-and-bound algorithm. The computational analysis shows that the branch-and-bound algorithm is quite efficient, especially when the setup and removal times are not too large compared to the processing times. Moreover, in the absence of removal times, the dominance property proposed by Dileepan appears to perform very well.
---
paper_title: Two models for a family of flowshop sequencing problems

paper_content:

Abstract This paper presents two mixed-integer linear programming (MILP) models (referred to as WST and SGST in the paper) for a family of four different M-machine, N -job flowshop sequencing problems. Each model may be used to solve the regular, no intermediate queues (NIQ), sequence-dependent setup times (SDST), and SDST/NIQ flowshop problems. The optimal job sequence, based on minimizing makespan, is achieved by a positional assignment approach in the WST model, and by pairs of disjunctive (either–or) constraints in the SGST model. A 12-cell experimental design was used to compare the solution times of the two models for each of the four flowshop problems. The WST model used significantly less computer time than the SGST model for all problem sizes in the regular, NIQ, and SDST flowshop problems. Both models were competitive in the SDST/NIQ flowshop for N ⩽7, but the WST model proved significantly better for N ⩾8.
---
paper_title: Scheduling a no-wait flowshop with separated setup and removal times

paper_content:

Consider the two-machine no-wait flowshop problem where the setup and removal times of a job at each machine are separated from the processing time. The scheduling objective is to minimize the sum of the total flowtime. Two optimization properties are first developed. In view of the NP-hard of this problem, optimal solutions seem unnecessary especially when the number of jobs is large. Then, combined the developed optimization properties with the greedy search a heuristic algorithm is developed. Computational experience demonstrates the effectiveness of the heuristic algorithm in finding near optimal schedules.
---
paper_title: A note on minimizing maximum lateness in a two-machine no-wait flowshop

paper_content:

Abstract Job scheduling for a two-machine flowshop where wait time between the first and the second machine is not permitted is studied in this paper. Aldowaisan and Allahverdi (J. Oper. Res. Soc. 53(9) (2002) 1004) considered this problem with minimizing total flowtime as the scheduling criterion and presented some necessary conditions for optimality. In this note their results have been modified for the scheduling criterion of minimizing maximum lateness.
---
paper_title: Flow Shop No-Wait Scheduling With Sequence Dependent Setup Times And Release Dates

paper_content:

We consider the problem of scheduling no-wait jobs, with release dates and sequence dependent setup times, on a flow shop to minimize the makespan. We show that this problem is equivalent to the asymmetric traveling salesman problem with additional visiting time constraints. For this latter problem we give a mathematical formulation and two lower bounds. Two heuristic algorithms for solving the scheduling problem are proposed. Performance analysis of both lower bounds and heuristics on randomly generated test problems are carried out.
---
paper_title: Total flowtime and makespan for a no-wait m-machine flowshop with set-up times separated

paper_content:

This paper addresses the m-machine no-wait flowshop problem where the set-up time of a job is separated from its processing time. The performance measures considered are the total flowtime and makespan. The scheduling problem for makespan reduces to the travelling salesman problem (TSP), and the scheduling problem for total flowtime reduces to the time-dependent travelling salesman problem (TDTSP). Non-polynomial time solution methods are presented, along with a polynomial heuristic.
---
paper_title: Scheduling for parallel dedicated machines with a single server

paper_content:

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule isNP-hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP-hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore{Gomory traveling salesman problem and solve it in polynomial time. c 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304{328, 2000
---
paper_title: Genetic algorithms for the no-wait flowshop sequencing problem with time restrictions

paper_content:

This article deals with the no-wait flowshop problem with sequence dependent set-ups and ready times solved by an evolutionary approach. The hybrid genetic algorithm presented here addresses a new hierarchically organized complete ternary tree to represent the population that put together with a recombination plan resembles a parallel processing scheme for solving combinatorial optimization problems. Embedded in the hybrid approach, a novel recursive local search scheme, recursive arc insertion (RAI), is also proposed. The effectiveness of the local search phase is crucial given that it is responsible for about 90% of the total processing time of the algorithm. Instances with known optimal solution are used to test the new algorithm and compare it to a previously proposed heuristic approach.
---
paper_title: Application of ant colony optimization for no-wait flowshop scheduling problem to minimize the total completion time

paper_content:

Ant colony optimization (ACO) is a meta-heuristic proposed to derive approximate solutions for computationally hard problems by emulating the natural behaviors of ants. In the literature, several successful applications have been reported for graph-based optimization problems, such as vehicle routing problems and traveling salesman problems. In this paper, we propose an application of the ACO to a two-machine flowshop scheduling problem. In the flowshop, no intermediate storage is available between two machines and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time. We first present a transformation of the scheduling problem into a graph-based model. An ACO algorithm is then developed with several specific features incorporated. A series of computational experiments is conducted by comparing our algorithm with previous heuristic algorithms. Numerical results evince that the ACO algorithm exhibits impressive performances with small error ratios. The results in the meantime demonstrate the success of ACO's applications to the scheduling problem of interest.
---
paper_title: Group scheduling in flexible flow shops

paper_content:

Abstract Flexible flow shops are becoming increasingly common in industry practice due to higher workloads imposed by jobs. As a result, one or more stages in a flexible flow shop will have two or more units of the same machine type. The group scheduling problem, comprised of two levels of scheduling, is investigated in this paper to minimize the makespan in a flexible flow shop. At the first level, a sequence of jobs in each group is determined, while at the second level a sequence of groups themselves is determined. A statistical model based on split-plot design is developed to conduct the experiments to compare the performance of three different heuristic solution algorithms. These comparisons are based on either single setup or multiple setups on machines for processing jobs in the same group. The single setup assumes that only one machine in a stage can be setup for a group, while the multiple setups assumes that more than one machine in a stage can be setup for a group. Three different problem structures representing sizes ranging from small, medium to large have been considered as the main factor along with flexibility introduced in the shop, setup-to-run time ratio, and solution algorithms as sub plot factors, thus resulting in a 34 factorial split-plot design. The higher the number of stages and the number of parallel machines in each stage, higher is the flexibility introduced in the shop. The results show that for small and medium size problems whether or not a computationally more demanding algorithm is employed to solve the level 1 or level 2 problem does not have any bearing on the makespan evaluated. This situation changes dramatically when large size problems are attempted, as a single-setup algorithm which combines the use of single- and multiple-pass heuristic for the level 2 and level 1 problems, respectively, outperforms another single-setup algorithm with the order of use reversed at all levels of flexibility. Test results also show that a multiple-setup algorithm is no worse than the single-setup algorithms and is sometimes much better. Hence, it is recommended for solving group scheduling problems in flexible flow shops.
---
paper_title: Scheduling a two-stage no-wait hybrid flowshop with separated setup and removal times

paper_content:

This paper studies the two-stage no-wait hybrid flowshop scheduling problem where one of the two stages consists of several identical parallel machines and the setup and removal times of each job at each stage are separated from the processing time. In view of the NP-complete of this problem, heuristic algorithms regarding sequencing and assigning of jobs to each stage as independent procedure are proposed. Two theorems are also proposed for sequencing job procedure. Computational experience demonstrates the effectiveness of the heuristic algorithm including the proposed theorems in finding a near optimal schedule.
---
paper_title: Simulated annealing heuristic for flow shop scheduling problems with unrelated parallel machines

paper_content:

This article addresses a multi-stage flow shop scheduling problem with unrelated parallel machines. Some practical processing restrictions such as independent setup and dependent removal times are taken into account as well. The objective is to minimize total flow time in the system. A simulated annealing (SA)-based heuristic is proposed to solve the addressed problem in a reasonable running time. The heuristic begins on a well-designed initial solution generator; then a simulated annealing procedure is applied for further improvement of the solution. To assure the quality and efficiency of the solution for the proposed SA-based heuristic, certain mechanisms are developed and introduced into the heuristic. The computational experimental results show that the proposed SA-based heuristic performs well with respect to accuracy and efficiency of solution.
---
paper_title: Scheduling jobs with uncertain setup times and sequence dependency

paper_content:

In many real-world job-shop situations, jobs are sequence dependent and the setup times for those jobs vary stochastically because of such random factors as crew skills, temporary shortage of equipment, tools and setup crews, and unexpected breakdowns of fixtures and tools during a setup operation. Assuming these random setup times to be fixed at, say, their expected values, which is often done in the extant literature, may lead to development of inefficient sequencing rules. The purpose of the present paper is to investigate the impact of setup-time variation on sequencing decisions, with normally-distributed setup times. Results show that setup-time variation has a negative impact on shop performance, but does not diminish the advantages of setup-conscious sequencing rules over conventional sequencing rules in dealing with setup times. A simulation model of a nine-machine job-shop is used in the investigation.
---
paper_title: A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility

paper_content:

After 50 years of research in the field of flowshop scheduling problems the scientific community still observes a noticeable gap between the theory and the practice of scheduling. In this paper we aim to provide a metaheuristic, in the form of a genetic algorithm, to a complex generalized flowshop scheduling problem that results from the addition of unrelated parallel machines at each stage, sequence dependent setup times and machine eligibility. Such a problem is common in the production of textiles and ceramic tiles. The proposed algorithm incorporates new characteristics and four new crossover operators. We show an extensive calibration of the different parameters and operators by means of experimental designs. To evaluate the proposed algorithm we present several adaptations of other well-known and recent metaheuristics to the problem and conduct several experiments with a set of 1320 random instances as well as with real data taken from companies of the ceramic tile manufacturing sector. The results indicate that the proposed algorithm is more effective than all other adaptations.
---
paper_title: Scheduling flexible flow lines with sequence-dependent setup times

paper_content:

Abstract This paper examines scheduling in flexible flow lines with sequence-dependent setup times to minimize makespan. This type of manufacturing environment is found in industries such as printed circuit board and automobile manufacture. An integer program that incorporates these aspects of the problem is formulated and discussed. Because of the difficulty in solving the IP directly, several heuristics are developed, based on greedy methods, flow line methods, the Insertion Heuristic for the Traveling Salesman Problem and the Random Keys Genetic Algorithm. Problem data is generated in order to evaluate the heuristics. The characteristics are chosen to reflect those used by previous researchers. A lower bound has been created in order to evaluate the heuristics, and is itself evaluated. An application of the Random Keys Genetic Algorithm is found to be very effective for the problems examined. Conclusions are then drawn and areas for future research are identified.
---
paper_title: An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times

paper_content:

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 deals with the hybrid flow shop scheduling problems in which there are sequence dependent setup times, commonly known as the SDST hybrid flow shops. This type of production system is found in industries such as chemical, textile, metallurgical, printed circuit board, and automobile manufacture. With the increase in manufacturing complexity, conventional scheduling techniques for generating a reasonable manufacturing schedule have become ineffective. An immune algorithm (IA) can be used to tackle complex problems and produce a reasonable manufacturing schedule within an acceptable time. This paper describes an immune algorithm approach to the scheduling of a SDST hybrid flow shop. An overview of the hybrid flow shops and the basic notions of an IA are first presented. Subsequently, the details of an IA approach are described and implemented. The results obtained are compared with those computed by Random Key Genetic Algorithm (RKGA) presented previously. From the results, it was established that IA outperformed RKGA.
---
paper_title: Comparing scheduling rules for flexible flow lines

paper_content:

Abstract This paper explores scheduling flexible flow lines with sequence-dependent setup times. Three major types of heuristics are explored. Insertion heuristics (based on insertion heuristics for the traveling salesman problem) attempt to simultaneously equalize workload on all processors at a stage, and minimize total or single-stage flowtimes. Johnson's algorithm for two-stage flow shops and its heuristic extensions to m-machine flow shops are modified for parallel processors and the flexible flow-line environment. A set of naive greedy heuristics is investigated for comparison purposes. The performance of the heuristics is compared on a set of test problems. Results indicate the range of conditions under which each method performs well.
---
paper_title: Scheduling Batches with Sequential Job Processing for Two-Machine Flow and Open Shops

paper_content:

In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these asconsistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested.
---
paper_title: The complexity of two group scheduling problems

paper_content:

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.
---
paper_title: A New Exact Solution Algorithm for the Job Shop Problem with Sequence-Dependent Setup Times

paper_content:

We propose a new solution approach for the Job Shop Problem with Sequence Dependent Setup Times (SDST-JSP). The problem consists in scheduling jobs, each job being a set of elementary operations to be processed on different machines. The objective pursued is to minimize the completion time of the set of operations. We investigate a relaxation of the problem related to the traveling salesman problem with time windows (TSPTW). Our approach is based on a Branch and Bound procedure, including constraint propagation and using this relaxation. It compares favorably over the best available approaches from the literature on a set of benchmark instances.
---
paper_title: A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups

paper_content:

Alternative operation sequences and sequence-dependent setups are two important factors that frequently appear in various manufacturing environments and in project scheduling. This paper addresses a jobshop scheduling problem with these factors simultaneously considered. In it, a mixed integer program model of the problem is presented, along with a local search scheme. The local search scheme utilizes a property identified to reduce computation time. In addition, a property that establishes a performance bound is presented. Results from a comparative computational study using benchmark data show that the scheme significantly enhances the performance of several greedy-based dispatching rules for the problem under consideration.
---
paper_title: A 6/5-approximation algorithm for the two-machine routing open-shop problem on a two-node network

paper_content:

Abstract In the routing open-shop problem, jobs are located at nodes of a transportation network, and the machines travel on the network to execute jobs. For the makespan-minimizing two-machine routing open-shop problem on a two-node network (which is NP-hard) we prove that the optimum objective value of any instance lies within the interval [ C ∼ , 6 5 C ∼ ] and this interval is tight. C ∼ is a trivial lower bound on the optimum objective value. Based on this result, we obtain a linear time approximation algorithm for this problem with approximation ratio not greater than 6 5 . From the tightness of the interval above it follows that this algorithm gives the best possible approximation in terms of C ∼ . The problem is equivalent to a variant of the two-machine open-shop problem with batch setup times with two batches.
---
paper_title: Using Genetic Algorithms and Heuristics for Job Shop Scheduling with Sequence-Dependent Setup Times

paper_content:

The importance of job shop scheduling as a practical problem has attracted the attention of many researchers. However, most research has focused on special cases such as single machine, parallel machine, and flowshop environments due to the “hardness” of general job shop problems. In this paper, a hybrid algorithm based on an integration of a genetic algorithm and heuristic rules is proposed for a general job shop scheduling problem with sequence-dependent setups (Jm|sjk|Cmax ). An embedded simulator is employed to implement the heuristic rules, which greatly enhances the flexibility of the algorithm. Knowledge relevant to the problem is inherent in the heuristic rules making the genetic algorithm more efficient, while the optimization procedure provided by the genetic algorithm makes the heuristic rules more effective. Extensive numerical experiments have been conducted and the results have shown that the hybrid approach is superior when compared to recently published existing methods for the same problem.
---
paper_title: Cyclic scheduling heuristics for a re-entrant job shop manufacturing environment

paper_content:

Two efficient cyclic scheduling heuristics for re-entrant job shop environments were developed. Each heuristic generated an efficient and feasible cyclic production schedule for a job shop in which a single product was produced repetitively on a set of machines was to determine an efficient and feasible cyclic schedule which simultaneously minimized flow time and cycle time. The first heuristic considered a repetitive production re-entrant job shop with a predetermined sequence of operations on a single product with known processing times, set-up and material handling times. The second heuristic was a specialization of the first heuristic where the set-up for an operation could commence even while the preceding operation was in progress. These heuristics have been extensively tested and computational results are provided. Also, extensive analysis of worst-case and trade-offs between cycle time and flow time are provided. The results indicate that the proposed heuristics are robust and yield efficient and ...
---
paper_title: A Petri net model and a general method for on and off-line multi-resource shop floor scheduling with setup times

paper_content:

Abstract This paper presents a Petri net model in the framework of a general method for on-line scheduling in a job shop environment with multi-resource requirements and setup times. The Petri net is based on a precise characterization of significant states, decisions and events for on- and off-line scheduling. A set of solutions to a static scheduling problem represented by an acyclic directed graph is assumed to be predetermined, as input of the proposed decision support system for shop floor scheduling. This system takes account of occurring events to suggest the appropriate scheduling decisions in real time and update the set of solutions accordingly.
---
paper_title: Modeling the reentrant job shop scheduling problem with setups for metaheuristic searches

paper_content:

We consider modeling the reentrant job shop scheduling problem with sequence dependent setup times in the context of metaheuristic search methods. We begin by investigating feasibility conditions when sequence dependent setups are incorporated into the traditional job shop scheduling problem. The investigation reveals that traditional methods of avoiding infeasible solutions for iterative search techniques do not suffice. The conditions under which these infeasible solutions occur are presented and an algorithm is presented to remove such infeasibilities. Reentrancy and its relationship to the traditional model are then illustrated, and the new features of the disjunctive graph are introduced. We conclude with a simple algorithm for obtaining an initial feasible solution, benefits of this research, and an application to the reentrant job shop scheduling problem with sequence dependent setups.
---
paper_title: Group technology approach to the open shop scheduling problem with batch setup times

paper_content:

This paper studies the problem of scheduling jobs in a two-machine open shop to minimize the makespan. Jobs are grouped into batches and are processed without preemption. A batch setup time on each machine is required before the first job is processed, and when a machine switches from processing a job in some batch to a job of another batch. For this NP-hard problem, we propose a linear-time heuristic algorithm that creates a group technology schedule, in which no batch is split into sub-batches. We demonstrate that our heuristic is a 54-approximation algorithm. Moreover, we show that no group technology algorithm can guarantee a worst-case performance ratio less than 54.
---
paper_title: Benefits of lot splitting in job-shop scheduling

paper_content:

As the lot-streaming concept has been used widely to reduce the makespan in a production system, most research has investigated the flow shop production systems; however, job-shop production systems have received much less attention, relatively. This study more thoroughly investigates the application of lot splitting in a job shop production system with setup times, which cannot be omitted. The objective investigated not only minimises the makespan but also minimises the total production cost, which includes the material handling cost, the setup cost and the inventory cost. A disjunctive graph is first used to describe the addressed scheduling problem, and an integer programming model is then constructed to obtain an optimal solution. In order to investigate the influence of the number of sublots and sublot sizes on a job-shop production system with regard to the corresponding objective considered, some experiments are conducted and results presented as well.
---
paper_title: Job-shop scheduling models with set-up times

paper_content:

In this paper we consider the classical representation of job-shop scheduling problems in terms of disjunctive graphs. We derive a mixed integer-linear programming model that keeps track of the immediate precedence relation between operations. Finally, we show how this framework can be used to solve job-shop scheduling problems with sequence-dependent set-up times. Two cases are considered: the set-up operation required before processing a job on a machine may start as soon as the machine is available, or only if both job and machine are available.
---
paper_title: Solving scheduling problems with setup times and alternative resources

paper_content:

In this paper a general shop scheduling problem with sequence dependent setup times and alternative resources is considered, where optimization criteria are both makespan and sum of setup times. Two cooperative models for the problem based on Constraint Programming are proposed. The first is used to model the scheduling constraints, while the second is a multi-path model used for setup optimization. Integrating lower bounding techniques for the sum of setup times, the multi-path model performs propagation based on reduced cost fixing. A solution method based on a two phase algorithm is described, and a computational study is performed both on instances known from literature as on newly proposed instances. It is shown that the cooperation of the two models significantly improves performance. Although the aim of the paper is to study the problem including alternative resources, for several known instances without alternative resources, we were able to improve on the best known results.
---
paper_title: Scheduling for parallel dedicated machines with a single server

paper_content:

This paper examines scheduling problems in which the setup phase of each operation needs to be attended by a single server, common for all jobs and different from the processing machines. The objective in each situation is to minimize the makespan. For the processing system consisting of two parallel dedicated machines we prove that the problem of finding an optimal schedule isNP-hard in the strong sense even if all setup times are equal or if all processing times are equal. For the case of m parallel dedicated machines, a simple greedy algorithm is shown to create a schedule with the makespan that is at most twice the optimum value. For the two machine case, an improved heuristic guarantees a tight worst-case ratio of 3/2. We also describe several polynomially solvable cases of the later problem. The two-machine flow shop and the open shop problems with a single server are also shown to be NP-hard in the strong sense. However, we reduce the two-machine flow shop no-wait problem with a single server to the Gilmore{Gomory traveling salesman problem and solve it in polynomial time. c 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 304{328, 2000
---
paper_title: Job shop scheduling with setup times, deadlines and precedence constraints

paper_content:

In the last 15 years several procedures have been developed that can find solutions of acceptable quality in reasonable computing time to Job Shop Scheduling problems in environments that do not involve sequence-dependent setup times of the machines. The presence of the latter, however, changes the picture dramatically. In this paper we adapt one of the best known heuristics, the Shifting Bottleneck Procedure, to the case when sequence dependent setup times play an important role. This is done by treating the single machine scheduling problems that arise in the process as Traveling Salesman Problems with time windows, and solving the latter by an efficient dynamic programming algorithm. The model treated here also incorporates precedence constraints, release times and deadlines. Computational experience on a vast array of instances, mainly from the semiconductor industry, shows our procedure to advance substantially the state of the art.
---
paper_title: One-operator, two-machine open shop and flow shop problems with setup times for machines and weighted number of tardy jobs objective

paper_content:

One-operator two-machine open shop and flow shop problems are 𝒩𝒫-hard in the ordinary sense even if all the weights are the same. We discuss two different pseudo polynomial dynamic programming recursions for each of the open shop and flow shop case. Some of the running times are better than those of the best known algorithms in the literature. †E-mail: rvickson@engmail.uwaterloo.ca
---
paper_title: A comparison of setup strategies for printed circuit board assembly

paper_content:

A two-phase procedure for configuring a cellular manufacturing system is proposed. In Phase I, a new similarity coefficient which considers the number of alternative routes when available during machine failure is proposed. The objective of Phase I is to identify part families based on the proposed new similarity coefficient. In Phase II, a new methodology which simultaneously considers scheduling and operational aspects in the cell design during machine failure for a manufacturing environment is proposed. Phase II shows how the scheduling and operational aspects influence the resource utilization during machine failure. The objective of the proposed methodology is to minimize the total sum of inventory holding cost, early/late finish penalty cost for each part in a given period, operating cost and machine investment cost by grouping machines into cells.
---
paper_title: A case study on the multistage IC final testing scheduling problem with reentry

paper_content:

Abstract The integrated-circuit final testing scheduling problem (ICFTSP) with reentry is a variation of the complex flow-shop scheduling problem, which is also a generalization of the classical reentrant flow batch process problem, and the identical parallel machine problem. In this paper, we present a case study on the ICFTSP with reentry, which is taken from a final testing shop floor in an integrated circuit manufacturing factory. For the case investigated, the jobs are clustered by their product types, which must be processed on groups of parallel machines at various process stages following the manufacturing sequence, which must be completed before the due dates. The job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. The objective is to schedule jobs without violating all constraints, while the total machine workload is minimized. Since the ICFTSP has reentry characteristic, and involves job processing precedence, serial-processing stage, batch-processing stage, job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequence dependent setup time, it is more difficult to solve than the classical flow-shop scheduling problem. We present three fast network algorithms to efficiently solve the ICFTSP with reentry and provide a performance comparison between the three algorithms on eight test problems.
---
paper_title: Scheduling a no-wait flowshop with separated setup and removal times

paper_content:

Consider the two-machine no-wait flowshop problem where the setup and removal times of a job at each machine are separated from the processing time. The scheduling objective is to minimize the sum of the total flowtime. Two optimization properties are first developed. In view of the NP-hard of this problem, optimal solutions seem unnecessary especially when the number of jobs is large. Then, combined the developed optimization properties with the greedy search a heuristic algorithm is developed. Computational experience demonstrates the effectiveness of the heuristic algorithm in finding near optimal schedules.
---
paper_title: Genetic algorithms applied in BOPP film scheduling problems: minimizing total absolute deviation and setup times

paper_content:

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.
---
paper_title: Scheduling of wafer test processes in semiconductor manufacturing

paper_content:

This research focuses on solving a common wafer test scheduling problem in semiconductor manufacturing. During wafer testing, a series of test processes are conducted on wafers using computer-controlled test stations at various temperatures. The test processes are conducted in a specified order on a wafer lot, resulting in precedence constraints for the schedule. Furthermore, the assignment of the wafer lots to test stations and the sequence in which they are processed affects the time required to set up the test operations. Thus, the set-up times are sequence dependent. Four heuristics are developed to solve the test scheduling problem with the aim of minimizing the makespan required to test all wafers on a set of test stations. The heuristics generate a sorted list of wafer lots as a dispatching sequence and then schedule the wafer lots on test stations in order of appearance on the list. An experimental analysis and two case studies are presented to validate the proposed solution approaches. In the cas...
---
paper_title: Minimizing the total machine workload for the wafer probing scheduling problem

paper_content:

The Wafer Probing Scheduling Problem (WPSP) is a practical generalization of the parallel-machine scheduling problem, which has many real-world applications, particularly, in the Integrated Circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which must be processed on groups of identical parallel machines and be completed before the due dates. The job processing time depends on the product type, and the machine setup time is sequentially dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequentially dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this paper, we consider the WPSP and formulate the WPSP as an integer programming problem to minimize the total machine workload. We demonstrate the applicability of the integer programming model by solving a real-world example taken from a wafer probing shop floor in an IC manufacturing factory.
---
paper_title: Production planning problems in printed circuit board assembly

paper_content:

This survey describes some of the main optimization problems arising in the context of production planning for the assembly of printed circuit boards. The discussion is structured around a hierarchical decomposition of the planning process into distinct optimization subproblems, addressing issues such as the assignment of board types to machine groups, the allocation of component feeders to individual machines, the determination of optimal production sequences, etc. The paper reviews the literature on this topic with an emphasis on the most recent developments, on the fundamental structure of the mathematical models and on the relation between these models and some 'environmental' variables such as the layout of the shop or the product mix.
---
paper_title: COMPARATIVE ANALYSIS OF ORDER-INPUT SEQUENCING HEURISTICS IN A CELLULAR FLEXIBLE ASSEMBLY SYSTEM FOR LARGE PRODUCTS

paper_content:

This study investigates the performance of order-input sequencing heuristics in a cellular flexible assembly system (CFAS) by computer simulation. The CFAS produces low-volume, large products in an assemble-to-order environment. This study examines two types of heuristic: two-stage (group scheduling) heuristics and single-stage heuristics. Two-stage heuristics attempt to serially process similar orders and eliminate major setups required between subfamilies. The results of the paired t -test analysis show that the two-stage heuristics outperform the single-stage heuristics under each experimental condition for various measures. The superior performance of the two-stage heuristics is due to the reduction in major setup times. The simulation results can provide guidance for schedulers in the selection of preferable heuristics for relevant CFASs.
---
paper_title: Scheduling a two-stage no-wait hybrid flowshop with separated setup and removal times

paper_content:

This paper studies the two-stage no-wait hybrid flowshop scheduling problem where one of the two stages consists of several identical parallel machines and the setup and removal times of each job at each stage are separated from the processing time. In view of the NP-complete of this problem, heuristic algorithms regarding sequencing and assigning of jobs to each stage as independent procedure are proposed. Two theorems are also proposed for sequencing job procedure. Computational experience demonstrates the effectiveness of the heuristic algorithm including the proposed theorems in finding a near optimal schedule.
---
paper_title: Improved dynamic programs for some batching problems involving the maximum lateness criterion

paper_content:

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.
---
paper_title: The wafer probing scheduling problem (WPSP)

paper_content:

The wafer probing scheduling problem (WPSP) is a variation of the parallel-machine scheduling problem, which has many real-world applications, particularly, in the integrated circuit (IC) manufacturing industry. In the wafer probing factories, the jobs are clustered by their product types, which must be processed on groups of identical parallel machines and be completed before the due dates. Further, the job processing time depends on the product type, and the machine setup time is sequence dependent on the orders of jobs processed. Since the wafer probing scheduling problem involves constraints on job clusters, job-cluster dependent processing time, due dates, machine capacity, and sequence dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problem. In this paper, we formulate the WPSP as an integer programming problem. We also transform the WPSP into the vehicle routing problem with time windows (VRPTW), a well-known network routing problem which has been investigated extensively. An illustrative example is given to demonstrate the proposed transformation. Based on the provided transformation, we present three efficient algorithms to solve the WPSP near-optimally.
---
paper_title: Asymptotically optimal schedules for single-server flow shop problems with setup costs and times

paper_content:

We consider the processing of M jobs in a flow shop with N stations in which only a single server is in charge of all stations. We demonstrate that for the objective of minimizing the total setup and holding cost, a class of easily implementable schedules is asymptotically optimal.
---
paper_title: A GENETIC ALGORITHM METHODOLOGY FOR COMPLEX SCHEDULING PROBLEMS

paper_content:

This paper considers the scheduling problem to minimize total tardiness given multiple machines, ready times, sequence dependent setups, machine downtime and scarce tools. We develop a genetic algorithm based on random keys representation, elitist reproduction, Bernoulli crossover and immigration type mutation. Convergence of the algorithm is proved. We present computational results on data sets from the auto industry. To demonstrate robustness of the approach, problems from the literature of different structure are solved by essentially the same algorithm.
---
paper_title: One-Operator, Two-Machine Open Shop And Flow Shop Scheduling With Setup Times For Machines And Maximum Lateness Objective

paper_content:

AbstractThis paper considers a scheduling problem in which a single operator completes a set of n jobs requiring operations on two machines. The operator can perform only one operation at a time, so when one machine is in use the other is idle. After developing general properties of optimal schedules, the paper develops efficient algorithms for minimizing maximum lateness. The algorithm has time complexity O(n) (after due date sorting) for both the open shop and How shop cases.
---
paper_title: The scheduling problem of PCBs for multiple non-identical parallel machines

paper_content:

Abstract The scheduling problem of n printed circuit boards (PCBs) for m non-identical parallel machines is considered in this paper. The problem has to deal with three issues: (i) classifying the PCBs into m groups corresponding to m machines, (ii) sequencing the boards for each machine, and (iii) component switching (component unloading/loading) from the machine magazine. A general objective is to minimize the total makespan, which is shown here to be the same as minimizing the maximum of number of component switches. The complete problem is complex, and is usually dealt in stages, which may not yield a good solution. We model the problem in an integrated manner using weighted multiple objectives to deal with grouping of the boards, load balancing at each machine, board sequencing and component switching at a machine. A composite genetic algorithm is developed to solve this multi-objective problem. The integrated solution is encoded as a string of pair values for each group of boards. The first number indicates the board membership in a group, and the second one represents the sequencing position of a board in that group. A new population of solutions is generated by using both binary genetic operators for grouping and genetic operators for board sequencing. A fitness function evaluates workload balancing, board similarities and total setup time simultaneously. Experiments are designed and run to test the proposed methodology, and the results show that the solutions are efficient, and are obtained within a reasonable amount of time.
---
paper_title: Scheduling a Single Server in a Two-machine Flow Shop

paper_content:

We study the problem of scheduling a single server that processes n jobs in a two-machine flow shop environment. A machine dependent setup time is needed whenever the server switches from one machine to the other. The problem with a given job sequence is shown to be reducible to a single machine batching problem. This result enables several cases of the server scheduling problem to be solved in O(n log n) by known algorithms, namely, finding a schedule feasible with respect to a given set of deadlines, minimizing the maximum lateness and, if the job processing times are agreeable, minimizing the total completion time. Minimizing the total weighted completion time is shown to be NP-hard in the strong sense. Two pseudopolynomial dynamic programming algorithms are presented for minimizing the weighted number of late jobs. Minimizing the number of late jobs is proved to be NP-hard even if setup times are equal and there are two ditstinct due dates. This problem is solved in O(n3) time when all job processing times on the first machine are equal, and it is solved in O(n4) time when all processing times on the second machine are equal.
---
paper_title: Algorithms for the wafer probing scheduling problem with sequence-dependent set-up time and due date restrictions

paper_content:

In this paper, we consider the wafer probing scheduling problem (WPSP) to sequence families of jobs on identical parallel machines with due date restrictions. The machine set-up time is sequentially dependent on the product types of the jobs processed on the machine. The objective is to minimize the total machine workload without violating the machine capacity and job due date restrictions. The WPSP is a variation of the classical parallel-machine scheduling problem, that can be transformed into the vehicle-routing problem with time windows (VRPTW). One can therefore solve the WPSP efficiently using existing VRPTW algorithms. We apply four existing savings algorithms presented in the literature including sequential, parallel, generalized, and matching based savings, and develop three modifications called the modified sequential, the compound matching based, and the modified compound matching-based savings algorithms, to solve the WPSP. Based on the characteristics of the wafer probing process, a set of test problems is generated for testing purposes. Computational results show that the three proposed modified algorithms perform remarkably well.
---
paper_title: Total flowtime and makespan for a no-wait m-machine flowshop with set-up times separated

paper_content:

This paper addresses the m-machine no-wait flowshop problem where the set-up time of a job is separated from its processing time. The performance measures considered are the total flowtime and makespan. The scheduling problem for makespan reduces to the travelling salesman problem (TSP), and the scheduling problem for total flowtime reduces to the time-dependent travelling salesman problem (TDTSP). Non-polynomial time solution methods are presented, along with a polynomial heuristic.
---
paper_title: A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops

paper_content:

Increases in the demand for integrated circuits have highlighted the importance of meeting customer quality and on-time delivery expectations in the semiconductor industry. A modified shifting bottleneck heuristic is developed for minimizing the total weighted tardiness in a semiconductor wafer fabrication facility. This ‘complex’ job shop is characterized by re-entrant or re-circulating product flow through a number of different tool groups (one or more machines operating in parallel). These tool groups typically contain batching machines, as well as machines that are subject to sequence-dependent setups. The disjunctive graph of the complex job shop is presented, along with a description of the proposed heuristic. Preliminary results indicate the heuristic's potential for promoting on-time deliveries by semiconductor manufacturers for their customers' orders. Copyright © 2002 John Wiley & Sons, Ltd.
---
paper_title: A tabu search approach to machine scheduling

paper_content:

Abstract In this paper we apply the tabu search (TS) technique to a complex machine scheduling problem. The problem can be considered as a generalization of the job-shop problem with both simple and parallel machines, job batches, setup times and release and due dates. The goal is to obtain feasible schedules by minimizing the makespan Cm,, if the problem is feasible, or to obtain a “best compromise” schedule if a full solution is not possible. The TS algorithm developed here is distinguished mainly by two aspects. Firstly, the core of the procedure is a tabu thresholding algorithm which uses a sophisticated set of moves aimed at resolving violated constraints. Secondly, the TS algorithm supplements the central tabu thresholding algorithm with two diversification strategies which are dependent on the state of the search. These strategies involve fairly major disruption of the schedules, and force significant diversification of the search. Computational experiments show that our algorithm can find high quality schedules in short running times
---
paper_title: Batching decisions for assembly production systems

paper_content:

The two-stage assembly scheduling problem is a model for production processes that involve the assembly of final or intermediate products from basic components. In our model, there are m machines at the first stage that work in parallel, and each produces a component of a job. When all components of a job are ready, an assembly machine at the second stage completes the job by assembling the components. We study problems with the objective of minimizing the makespan, under two different types of batching that occur in some manufacturing environments. For one type, the time to process a batch on a machine is equal to the maximum of the processing times of its operations. For the other type, the batch processing time is defined as the sum of the processing times of its operations, and a setup time is required on a machine before each batch. For both models, we assume a batch availability policy, i.e., the completion times of the operations in a batch are defined to be equal to the batch completion time. We provide a fairly comprehensive complexity classification of the problems under the first type of batching, and we present a heuristic and its worst-case analysis under the second type of batching.
---
paper_title: Scheduling Batches with Sequential Job Processing for Two-Machine Flow and Open Shops

paper_content:

In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these asconsistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested.
---
paper_title: The complexity of two group scheduling problems

paper_content:

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.
---
paper_title: A New Exact Solution Algorithm for the Job Shop Problem with Sequence-Dependent Setup Times

paper_content:

We propose a new solution approach for the Job Shop Problem with Sequence Dependent Setup Times (SDST-JSP). The problem consists in scheduling jobs, each job being a set of elementary operations to be processed on different machines. The objective pursued is to minimize the completion time of the set of operations. We investigate a relaxation of the problem related to the traveling salesman problem with time windows (TSPTW). Our approach is based on a Branch and Bound procedure, including constraint propagation and using this relaxation. It compares favorably over the best available approaches from the literature on a set of benchmark instances.
---
paper_title: A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups

paper_content:

Alternative operation sequences and sequence-dependent setups are two important factors that frequently appear in various manufacturing environments and in project scheduling. This paper addresses a jobshop scheduling problem with these factors simultaneously considered. In it, a mixed integer program model of the problem is presented, along with a local search scheme. The local search scheme utilizes a property identified to reduce computation time. In addition, a property that establishes a performance bound is presented. Results from a comparative computational study using benchmark data show that the scheme significantly enhances the performance of several greedy-based dispatching rules for the problem under consideration.
---
paper_title: Lot splitting to minimize average flow-time in a two-machine flow-shop

paper_content:

Lot splitting is a technique for accelerating the flow of work by splitting job lots into sublots, In this paper we investigate the lot splitting scheduling problem in a two-machine flow-shop environment with detached setups and with batch availability. The performance measure considered is the average flow-time which is indicative of the increasingly important manufacturing lead-time. Our contribution is both theoretic and practical for the case of general (not necessarily equal) sublots. We identify properties of the optimal solution and develop a solution procedure to solve the problem. We then present a computational study which indicates that our solution technique is very efficient.
---
paper_title: One-Operator, Two-Machine Open Shop And Flow Shop Scheduling With Setup Times For Machines And Maximum Lateness Objective

paper_content:

AbstractThis paper considers a scheduling problem in which a single operator completes a set of n jobs requiring operations on two machines. The operator can perform only one operation at a time, so when one machine is in use the other is idle. After developing general properties of optimal schedules, the paper develops efficient algorithms for minimizing maximum lateness. The algorithm has time complexity O(n) (after due date sorting) for both the open shop and How shop cases.
---
paper_title: Modeling the reentrant job shop scheduling problem with setups for metaheuristic searches

paper_content:

We consider modeling the reentrant job shop scheduling problem with sequence dependent setup times in the context of metaheuristic search methods. We begin by investigating feasibility conditions when sequence dependent setups are incorporated into the traditional job shop scheduling problem. The investigation reveals that traditional methods of avoiding infeasible solutions for iterative search techniques do not suffice. The conditions under which these infeasible solutions occur are presented and an algorithm is presented to remove such infeasibilities. Reentrancy and its relationship to the traditional model are then illustrated, and the new features of the disjunctive graph are introduced. We conclude with a simple algorithm for obtaining an initial feasible solution, benefits of this research, and an application to the reentrant job shop scheduling problem with sequence dependent setups.
---
paper_title: Job-shop scheduling models with set-up times

paper_content:

In this paper we consider the classical representation of job-shop scheduling problems in terms of disjunctive graphs. We derive a mixed integer-linear programming model that keeps track of the immediate precedence relation between operations. Finally, we show how this framework can be used to solve job-shop scheduling problems with sequence-dependent set-up times. Two cases are considered: the set-up operation required before processing a job on a machine may start as soon as the machine is available, or only if both job and machine are available.
---
paper_title: Flow-shop batch scheduling with identical processing-time jobs

paper_content:

In many practical situations of production scheduling, it is either necessary or recommended to group a large number of jobs into a relatively small number of batches. A decision needs to be made regarding both the batching (i.e., determining the number and the size of the batches) and the sequencing (of batches and of jobs within batches). A setup cost is incurred whenever a batch begins processing on a given machine. This paper focuses on batch scheduling of identical processing-time jobs, and machine- and sequence-independent setup times on an m-machine flow-shop. The objective is to find an allocation to batches and their schedule in order to minimize flow-time. We introduce a surprising and nonintuitive solution for the problem. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004
---
paper_title: Job shop scheduling with setup times, deadlines and precedence constraints

paper_content:

In the last 15 years several procedures have been developed that can find solutions of acceptable quality in reasonable computing time to Job Shop Scheduling problems in environments that do not involve sequence-dependent setup times of the machines. The presence of the latter, however, changes the picture dramatically. In this paper we adapt one of the best known heuristics, the Shifting Bottleneck Procedure, to the case when sequence dependent setup times play an important role. This is done by treating the single machine scheduling problems that arise in the process as Traveling Salesman Problems with time windows, and solving the latter by an efficient dynamic programming algorithm. The model treated here also incorporates precedence constraints, release times and deadlines. Computational experience on a vast array of instances, mainly from the semiconductor industry, shows our procedure to advance substantially the state of the art.
---

Title: A Survey of Scheduling Problems with Setup Times or Costs

Section 1: Introduction
Description 1: This section introduces the topic of scheduling problems, historical context, the need for considering setup times or costs, and objectives of the survey.

Section 2: Notation and Classification
Description 2: This section provides the necessary notation and classification for the scheduling problems with setup times/costs discussed in the paper.

Section 3: Scheduling Problems with Setup Times or Costs
Description 3: This section is divided into sub-sections covering different types of scheduling problems such as batch and non-batch, sequence-independent and sequence-dependent, with extensive literature reviews for each type.

Section 4: Single Machine
Description 4: This section describes the literature related to single machine scheduling problems including batch and sequence-dependent setup times with tables summarizing key contributions.

Section 5: Parallel Machines
Description 5: This section covers scheduling problems in parallel machine environments, outlining various algorithms, heuristics, and solution approaches relevant to batch and sequence-dependent setup times.

Section 6: Flow Shops
Description 6: This section includes discussions on scheduling problems in different types of flow shops such as regular flow shop, no-wait flow shop, and flexible/hybrid flow shop environments.

Section 7: Job Shop and Open Shop
Description 7: This section reviews the literature on job shop and open shop scheduling problems, highlighting significant algorithms and complexity results.

Section 8: Others
Description 8: This section discusses miscellaneous scheduling scenarios and specific industrial applications such as production lines, cellular systems, and other case studies.

Section 9: Conclusions
Description 9: This section summarizes the findings of the survey, trends in current research, open problems, and suggestions for future research directions.