Evaluating the performance of tabu search procedures for flow shop sequencing
- PDF / 202,046 Bytes
- 7 Pages / 595 x 842 pts (A4) Page_size
- 104 Downloads / 195 Views
#1998 Operational Research Society Ltd. All rights reserved. 0160-5682/98 $12.00 http://www.stockton-press.co.uk/jor
Evaluating the performance of tabu search procedures for ¯ow shop sequencing JV Moccellin and MS Nagano University of SaÄo Paulo, Brazil We address the problem of minimising makespan in a ¯ow shop by using tabu search procedures. By combining different neighbourhood structures, neighbourhood examinations, and stopping conditions we obtain alternative tabu search procedures. Starting from a common initial solution we evaluate the relative performance of such procedures considering both the solution quality and computational effort. Keywords: ¯ow shop sequencing; heuristics; tabu search
Introduction The general ¯ow shop scheduling problem is a production problem where a set of n jobs have to be processed with identical ¯ow pattern on m machines. When the sequence of job processing on all machines is the same we have the Flow Shop Sequencing production environment. Since there is no job passing, the number of possible schedules for n jobs is n!. Usually the schedule performance measure is related to an ef®cient resource utilisation looking for a job sequence that minimises the makespan, that is the total time to complete the schedule. This scheduling problem is generally modelled on the following assumptions: (i) The operation processing times on the machines are known, ®xed and some of them may be zero if some job is not processed on a machine; (ii) Set-up times are included in the processing times and they are independent of the job position in the sequence of jobs; (iii) At a time, every job is processed on only one machine, and every machine processes only one job; (iv) The job operations on the machines may not be preempted. A signi®cant research effort has been devoted for sequencing jobs in a ¯ow shop with the objective of ®nding a sequence that minimises the makespan. For problems with two machines, or three machines under speci®c constraints on job processing times, the ef®cient Johnson's algorithm1 obtains an optimal solution. However, since this scheduling problem is NP-hard the search for an optimal solution is of more theoretical than practical importance. Having this in mind, since the 1960s a number of heuristic methods that provide near optimal or good solutions with limited computational effort have been proposed for ¯ow
Correspondence: Dr JV Moccellin, SEM±Engenharia de ProducËaÄo EESCUSP, Av. Dr. Carlos Botelho, 1465, 13560-250±SaÄo Carlos±SP, Brasil E-mail: [email protected]
shop sequencing. For instance: Palmer,2 Campbell et al,3 Gupta,4 Dannenbring,5, Nawaz et al.,6 Widmer and Hertz,7 Osman and Potts,8 Taillard,9 Ogbu and Smith,10,11 Reeves,12,13 Moccellin,14 Nowicki and Smutnicki,15 Lai,16 Sundararaghavan et al,17 and Koulamas.18 In the paper of Moccellin,14 was presented a heuristic named FSHOPH, whose basic steps are: (1) Get an initial solution for the ¯ow shop sequencing problem by using an analogy with the travelling salesman problem, in which the `distance' bet
Data Loading...
