Two-machine open shop scheduling with secondary criteria

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 herusitic 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.