AbstractNegotiating and meeting due-times for work-orders is often the most important concern of managers of manufacturing systems. We propose 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. We propose 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, we characterise the solution space and present experimental results on the performances of several heuristics.