Skip to Main content Skip to Navigation

Multi-product lot-sizing and sequencing on unrelated parallel machines

Abstract : We study a problem of optimal scheduling and lot-sizing a number of products on m unrelated parallel machines to satisfy given demands. A sequence dependent setup time is required between lots of di erent products. The products are assumed to be all continuously divisible or all discrete. The criterion is to minimize the time, at which all the demands are satis ed, Cmax; or the maximum lateness of the product completion times from the given due dates, Lmax: The problem is motivated by the real-life scheduling applications in multiproduct plants. We derive properties of optimal solutions, NP-hardness proofs, enumeration and dynamic programming algorithms for various special cases of the problem. The major contribution is an NP-hardness proof and pseudo-polynomial algorithms linear in m for the case, in which the number of products is a given constant. The results can be adapted for solving a production line design problem.
Document type :
Complete list of metadata
Contributor : Florent Breuil Connect in order to contact the contributor
Submitted on : Friday, March 16, 2012 - 2:17:19 PM
Last modification on : Wednesday, August 4, 2021 - 3:42:04 PM


  • HAL Id : emse-00679831, version 1


Alexandre Dolgui, Anton Eremeev, Mikhail Y. Kovalyov. Multi-product lot-sizing and sequencing on unrelated parallel machines. 2007. ⟨emse-00679831⟩



Record views