Zurück zu den Preprints des Jahres 2000


2000-23

Open Shop Scheduling with Secondary Criteria

by Gupta, J.N.D., Werner, F., Wulkenhaar, G..


Series: 2000-23, Preprints

MSC:
90B35 Scheduling theory, deterministic

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

This paper was published in:
International Transa