Premium
Two‐machine open shop scheduling with secondary criteria
Author(s) -
Gupta Jatinder N. D.,
Werner Frank,
Wulkenhaar Gunnar
Publication year - 2003
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/1475-3995.00407
Subject(s) - tardiness , mathematical optimization , job shop scheduling , minification , computer science , simulated annealing , constructive , heuristic , flow shop scheduling , scheduling (production processes) , mathematics , algorithm , schedule , process (computing) , operating system
This paper considers two‐machine open shop problems with secondary criteria where 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 polynomially 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.