Minimizing Makespan on Parallel Machines Subject to Release Dates and Delivery Times

Journal Article

Gharbi, Anis . 2002

• Publication Online URL: Minimizing Makespan on Parallel Machines Subject to Release Dates and Delivery Times
• Tags: scheduling, identical parallel machines, makespan, release dates, delivery times, branch-and-bound
• Magazine \ Newspaper: Journal of Scheduling
• Issue Number: 4
• Volume Number: 5
• Pages: 329–355

Publication Abstract

We consider the problem of minimizing the makespan on identical parallel machines subject to release dates and delivery times. The objective of this paper is to develop exact branch-and-bound algorithms to solve this strongly NP-hard problem. A preprocessing algorithm is devised to speed up the convergence of the proposed algorithms, and a new tight bounding scheme is introduced. The search tree is also reduced using a polynomial selection algorithm. Extensive computational experiments show that instances with up to 300 jobs can be solved exactly in a moderate CPU time.