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
Complexity
Branch-and-bound
Dynamic programming
Lagrangian relaxation
Résumé
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.