Query: Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

Candidate papers:

abstract: In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches.
author_names: Rene Driessel

Lars Monch
title: Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence dependent setup times, precedence constraints, and ready times
venue: Comput. Ind. Eng.
year: 2011

abstract: In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness. Scheduling problems of this type are quite important in semiconductor manufacturing. We suggest a variable neighborhood search (VNS) scheme for this problem. Based on computational experiments with stochastically generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule in many situations.
author_names: Rene Driessel

Lars Moench
title: Scheduling jobs on parallel machines with sequence dependent setup times, precedence constraints, and ready times using variable neighborhood search
venue: 2009 International Conference on Computers Industrial Engineering
year: 2009

abstract: The study considers the scheduling problem of identical parallel machines subject to minimization of the maximum completion time and the maximum tardiness expressed in a linear convex objective function. The maximum completion time or makespan is the date when the last job to be completed leaves the system. The maximum tardiness is indicated by the job that is completed with the longest delay relative its due date. Minimizing both criteria can help assuring a high utilization of the production system as well as a high level of service towards the client. Due to the complexity of the problem, a Simulated Annealing (SA) heuristic has been implemented to be able to obtain an efficient solution in a reasonable running time. A set of n jobs is assigned, to one of the m identical parallel machines. Each job is processed in only one operation before its completion after which it leaves the system. Constraints, such as due dates for each job and setup times for the machines, are considered. The resolution procedure consists of two phases and begins with an initial solution generator. Then a SA heuristic is applied for further improvement of the solution. 4 generators are used to create an initial solution and 3 to generate neighbour solutions. To test and verify the performance of the proposed resolution procedure, a computational experimentation has been realized on a set of test problems generated ad hoc.
author_names: Rasmus Persson
title: A Bicriteria Simulated Annealing Algorithm for Scheduling Jobs on Parallel Machines with Sequence Dependent Setup Times
year: 2008

abstract: 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.
author_names: Mary E Kurz

Ronald G Askin
title: Scheduling flexible flow lines with sequence dependent setup times
venue: Eur. J. Oper. Res.
year: 2004

abstract: This paper presents a novel, multi objective model of a parallel machines scheduling problem that minimizes the number of tardy jobs and total completion time of all jobs. In this model, machines are considered as unrelated parallel units with different speeds. In addition, there is some precedence, relating the jobs with non identical due dates and their ready times. Sequence dependent setup times embedded in the proposed model may vary in different machines based on their characteristics. This paper proposes a two level mixed integer programming for the given problem. By solving the presented model, the associated promising results show the effectiveness of this model for small and medium sized problems, respectively.
author_names: Reza Tavakkoli-Moghaddam

Mohammad Bazzazi
title: MULTI OBJECTIVE UNRELATED PARALLEL MACHINES SCHEDULING WITH SEQUENCE DEPENDENT SETUP TIMES AND PRECEDENCE CONSTRAINTS
year: 2008

abstract: 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.
author_names: Mostafa Zandieh

Seyed Mohammad Taghi Fatemi Ghomi

S M Moattar Husseini
title: An immune algorithm approach to hybrid flow shops scheduling with sequence dependent setup times
venue: Appl. Math. Comput.
year: 2006

abstract: Abstract 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.
author_names: Nagraj Balakrishnan

John J Kanet

Sri V Sridharan
title: Early/tardy scheduling with sequence dependent setups on uniform parallel machines
venue: Comput. Oper. Res.
year: 1999

abstract: Each of a collection of items are to be produced on two machines (or stages) Each machine can handle only one item at a time and each item must be processed through machine one and then through machine two. The setup time plus work time for each item for each machine is known. A simple decision rule is obtained in this paper for the optimal scheduling of the production so that the total elapsed time is a minimum. A three machine problem is also discussed and solved for a restricted case.
author_names: S M Johnson
title: Optimal two and three stage production schedules with setup times included
year: 1954

abstract: In this paper a multicriteria scheduling problem with sequence dependent setup times on a single machine is considered. The objective function of the problem is minimization of the weighted sum of total completion time, maximum tardiness and maximum earliness. An integer programming model is developed for the problem which belongs to NP hard class. Only small size problems with up to 12 jobs can be solved by the proposed integer programming model. Heuristic methods are also used to solve large size problems. These heuristics are four tabu search based heuristics and random search method. According to computational results the tabu search based methods are effective in finding problem solutions with up to 1000 jobs.
author_names: Tamer Eren
title: A Multicriteria Scheduling with Sequence Dependent Setup Times
year: 2007

abstract: 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 can be either symmetric or asymmetric but must satisfy the triangle inequality. A modified insertion heuristic is found to perform best for these types of problems.
author_names: Mary E Kurz

Ronald G Askin
title: Heuristic scheduling of parallel machines with sequence dependent set up times
year: 2001