WRLSP: A Single-Machine, Warehouse Restricted Lot Scheduling Problem

Abstract

This paper treats a single-machine, multi-product scheduling problem arising from an application in an automobile factory. The problem is to sequence the production lots of N products in a common cycle schedule to minimize the maximum storage space required by the machine's output, given constant production and demand rates, sequence-independent setup times and sharing of the storage space among the products. As the problem is strongly NP-hard, a heuristic and a branch and bound algorithm are developed for solving it. The algorithms are assessed on a set of random test problems similar in size and complexity to the original application.