Skema > Faculty and Research > Publication-details





Minimizing makespan on a single machine with release dates and inventory constraints
Mohammad Ranjbar
Patrick De Causmaecker
Roel Leus
2020, European Journal of Operational Research, 286(1), pp.115-128
Single-machine scheduling
Inventory constraint
Dynamic programming
Lagrangian relaxation
We consider a single-machine scheduling problem with release dates and inventory constraints. Each job has a deterministic processing time and has an impact (either positive or negative) on the central inventory level. We aim to find a sequence of jobs such that the makespan is minimized while all release dates and inventory constraints are met. We show that the problem is strongly NP-hard even when the capacity of the inventory is infinite. To solve the problem, we introduce a time-indexed formulation and a sequence-based formulation, a branch-and-bound algorithm, and a dynamic-programming-based guess-and-check (GC) algorithm. From extensive computational experiments, we find that the GC algorithm outperforms all other alternatives.

Why choose SKEMA?
At the top of French and international rankings SEE RANKINGS
A global business school SEE SKEMA NEWS
A wide range of programmes COMPARE