Overtime scheduling: An application in finite-capacity real-time scheduling

Negotiating and meeting due-times for work-orders is often the most important concern of managers of manufacturing systems. This paper proposes a new approach called overtime scheduling that determines on which work-centres, when and how much overtime is required to meet a requested due-time with minimum overtime cost. This method would be used as a part of a finite-capacity real-time scheduling and planning system. The paper proposes a work-order insertion based approach, where a new work-order is scheduled without substantially changing the schedule of previously scheduled work-orders. Based on this approach the solution space is characterised and present experimental results on the performances of several heuristics.