Heuristic scheduling of parallel machines with sequence-dependent set-up times
Authors:
- M. E. KurzMKM. E. Kurz
- R. G. AskinRAR. G. Askin
- 1 January 2001
- journal article
- research article
- Published by Taylor & Francis in International Journal of Production Research
- Vol. 39 (16) , 3747-3769
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.Keywords
This publication has 27 references indexed in Scilit:
- Scheduling multiprocessor tasks with genetic algorithmsIEEE Transactions on Parallel and Distributed Systems, 1999
- Thek-partitioning problemMathematical Methods of Operations Research, 1998
- New Algorithms for an Ancient Scheduling ProblemJournal of Computer and System Sciences, 1995
- Minmax combinatorial optimizationEuropean Journal of Operational Research, 1995
- A genetic algorithm for multiprocessor schedulingIEEE Transactions on Parallel and Distributed Systems, 1994
- On scheduling parallel machines with two setup classesInternational Journal of Production Research, 1991
- Scheduling batches on parallel machines with major and minor set-upsEuropean Journal of Operational Research, 1990
- On the Use of A Vehicle Routing Algorithm for the Parallel Processor Problem with Sequence Dependent Changeover CostsA I I E Transactions, 1977
- Algorithms for Scheduling Independent TasksJournal of the ACM, 1976
- Preemptive Scheduling of Real-Time Tasks on Multiprocessor SystemsJournal of the ACM, 1970