On Multi-product Lot-Sizing and Scheduling with Multi-machine Technologies

Anton V. Eremeev () and Julia V. Kovalenko ()
Additional contact information
Anton V. Eremeev: Omsk Branch of Sobolev Institute of Mathematics SB RAS
Julia V. Kovalenko: Omsk Law Academy

A chapter in Operations Research Proceedings 2014, 2016, pp 301-306 from Springer

Abstract: Abstract We consider a problem of multi-product lot-sizing and scheduling where each product can be produced by a family of alternative multi-machine technologies. Multi-machine technologies require one or more machine at the same time. A sequence dependent setup time is needed between different technologies. The criterion is to minimize the makespan. Preemptive and non-preemptive versions of the problem are studied. We formulate mixed integer linear programming models based on a continuous time representation for both versions of the problem. Using these models, the polynomially solvable cases of the problem are found. It is proved that the problem without setup times is strongly NP-hard if there is only one product, and each technology occupies at most three machines. Besides that, problem cannot be approximated within a practically relevant factor of the optimum in polynomial time, if P $$\ne $$ ≠ NP.

Keywords: Schedule Problem; Completion Time; Setup Time; Mixed Integer Linear Programming; Boolean Variable (search for similar items in EconPapers)
Date: 2016
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-319-28697-6_42

Ordering information: This item can be ordered from
http://www.springer.com/9783319286976

DOI: 10.1007/978-3-319-28697-6_42

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().