A tabu search approach for the single machine mean tardiness problem
- PDF / 234,945 Bytes
- 5 Pages / 595 x 842 pts (A4) Page_size
- 107 Downloads / 176 Views
#1997 Operational Research Society Ltd. All rights reserved. 0160-5682/97 $12.00
A tabu search approach for the single machine mean tardiness problem A Islam and M Eksioglu Wichita State University, USA In this paper, a tabu search approach is proposed for solving the single machine mean tardiness scheduling problem. Simulation experiment results obtained from the tabu search approach and three other heuristics are compared. Although computation time is increased, the results indicate that the proposed approach provides a much better solution than the other three approaches. Keywords: tabu search; heuristics; mean tardiness; single machine scheduling
Introduction
The description of the problem
This paper presents a tabu search procedure for minimizing the mean tardiness on a single machine. Single-machine scheduling does not necessarily involve one machine. It can also involve a group of machines or a system that can be treated as one machine, such as serial production lines scheduled as a single unit. In addition, high-tech manufacturing facilities, such as computer controlled machining centres and robotic cells that can be treated as single machines for scheduling purposes are also often seen in industry. Minimizing the mean tardiness is one of the most important criteria in single-machine scheduling and it is NP-hard.1 Optimal solutions to the scheduling problem can be obtained through the enumeration methods, such as dynamic programming and branch-and-bound. These optimal techniques, however, may take a tremendous amount of computation time and require a powerful computer. Hence, efforts have been intensi®ed in developing heuristic procedures. Heuristics such as Fry et al,2 Holsenback and Russell,3 and simulated annealing have been the most successful for solving the one-machine scheduling problem so far. In this study, we propose and implement a tabu search approach for solving the one-machine scheduling problem where it is required to minimize mean tardiness. The results are compared with those of the three most successful heuristics.
The single-machine mean tardiness scheduling problem can be described as follows: at time zero, there exist n jobs simultaneously in a queue to be processed on a single machine. Each job has its processing time ( p) and its due date (d). The goal is to ®nd a processing sequence from the n! possible sequences that minimizes the mean tardiness (T ) de®ned as follows: n 1 P max0; Ci ÿ di T n i1 where n number of jobs Ci completion time; of ith job di due date of ith job The following assumptions presented by Conway et al 4 and accepted by most researchers are adopted for the considered problem: pi is an integer and is sequence independent, di is an integer measured from time zero when all jobs are available for processing, the machine is available continuously to process n jobs, and there are no setup times or time loss due to machine loading and unloading. Algorithms for single machine scheduling
Correspondence: Dr A Islam, Department of Industrial and
Data Loading...
