00-23
Open Shop Scheduling with Secondary Criteria
by Gupta, J.N.D.; Werner, F.; Wulkenhaar, G.
Preprint series: 00-23, Preprints
The paper is published: International Transactions in Operational Research, Vol. 10, No. 3, 2003, 267 - 294.
Abstract: The paper considers two-machine open-shop problems with secondary criteria when the primary criterion is the minimization of makespan and the secondary criterion is the minimization of the total flow time, total weighted flow time, or total weighted tardiness time. In view of the strongly NP-hard nature of these problems, two poynomially solvable special cases are given and constructive heuristic algorithms based on insertion techniques are developed. A strongly connected neighborhood structure is derived and used to develop effective iterative heuristic algorithms by incorporating iterative improvement, simulated annealing and multi-start procedures. The proposed insertion and iterative heuristic algorithms are empirically evaluated by solving problem instances with up to 80 jobs.
Keywords: Open shop scheduling, Secondary criteria, Constructive and iterative heuristics
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.