Premium
Tight bounds for the identical parallel machine scheduling problem
Author(s) -
Haouari Mohamed,
Gharbi Anis,
Jemmali Mahdi
Publication year - 2006
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/j.1475-3995.2006.00562.x
Subject(s) - heuristics , bounding overwatch , job shop scheduling , computer science , mathematical optimization , scheduling (production processes) , upper and lower bounds , branch and bound , algorithm , mathematics , artificial intelligence , schedule , mathematical analysis , operating system
We address the problem of minimizing makespan on identical parallel machines. We propose new lower bounding strategies and heuristics for this fundamental scheduling problem. The lower bounds are based on the so‐called lifting procedure. In addition, two optimization‐based heuristics are proposed. These heuristics require iteratively solving a subset‐sum problem. We present the results of computational experiments that provide strong evidence that the new proposed lower and upper bounds consistently outperform the best bounds from the literature.