 Minimizing makespan on a single machine with release dates and inventory constraintsMorteza Davari, Mohammad Ranjbar, Patrick De Causmaecker and Roel Leus European Journal of Operational Research, 2020, vol. 286, issue 1, 115-128 Abstract: 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. Keywords: Single-machine scheduling; Inventory constraint; Complexity; Branch-and-bound; Dynamic programming; Lagrangian relaxation (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:286:y:2020:i:1:p:115-128 DOI: 10.1016/j.ejor.2020.03.029 Access Statistics for this article European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati More articles in European Journal of Operational Research from Elsevier |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.