A New Heuristic for a Single Machine Scheduling Problem with Set-up Times |
| |
Authors: | David Williams Andrew Wirth |
| |
Affiliation: | 1.University of British Columbia,Canada;2.University of Melbourne,Australia |
| |
Abstract: | This paper examines the problem of scheduling jobs on a single machine with set-up times. The jobs are divided into mutually exclusive classes and a set-up task is required when processing switches from a job of one class to a job of another class. The set-up times are assumed to be sequence independent. A number of necessary conditions for a schedule to minimize mean flow time have previously been stated, but do not uniquely define the optimal solution, and the problem is apparently NP-complete. We propose a new polynomial-time heuristic, based on these conditions, and compare its performance with some existing heuristics. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|