A parallel machine lot-sizing and scheduling problem with a secondary resource and cumulative demand

Abstract

We investigate a parallel machine multi-item lot-sizing and scheduling problem with a secondary resource, in which demands are given for the entire planning horizon rather than for every single period. All-or-nothing assumption of the discrete lot-sizing and scheduling problem is valid so that a machine is either idle or works at full capacity in a period. The objective is to minimise the number of setups and teardowns. We prove that the problem is NP-hard and present two equivalent formulations. We show some properties of the optimal objective value, give optimality conditions and suggest a heuristic algorithm. We discuss and formulate two possible extensions related to real-life applications. Finally, we carry out computational experiments to compare the two formulations, to determine the effect of our proposed modeling improvements on solution performance, and to test the quality of our heuristic.

Keywords:

• lot-sizing
• scheduling
• parallel machines
• mixed integer linear programming
• secondary resource
• cumulative demand

Notes

No potential conflict of interest was reported by the authors.