Multi-Product Lot-Sizing and Scheduling on Unrelated Parallel Machines to Minimize Makespan

International audienceWe study a problem of optimal scheduling and lot-sizing a number of products on m unrelated parallel machines to satisfy given demands, minimizing the makespan criterion. A sequence dependent setup time is required between lots of different products. The products are assumed to be all continuously divisible or all discrete. The problem is motivated by the real-life scheduling applications in multi-product plants. We derive properties of optimal solutions, NP-hardness proof, enumeration and dynamic programming algorithms for various special cases of the problem. A greedy-type heuristic is proposed and tested in computational experiments