Performance Evaluation of a Hierarchical Production Scheduling Policy for a Single Machine with Earliness and Tardiness

Abstract

This paper considers the problem of scheduling a given set of jobs on a single machine in order to minimize the total earliness and tardiness costs. The scheduling horizon is divided into elementary periods; jobs have due-dates at the end of these periods. All jobs are assumed initially available. Jobs have unique (weighted) early and tardy penalty functions that are staircase-type. No preemption of jobs is permitted, and idle time may be inserted. This problem is NP-complete. A branch- and-bound scheme that solves the above mentioned problem optimally is presented. We then propose a hierarchical scheduling policy under the assumption that tardiness costs are much greater than earliness costs for all jobs. We also assume that the system if able to meet the production requirements on the average and the scheduling horizon is long enough to absorb cyclicity. The hierarchy is composed of two levels: (i) the high level, and (ii) the low level. The concept of rolling horizon is employed at the high level, which solves the flow control under constraints of no tardiness. The low level, prioritizes jobs resulting from the solution of the high level over a short term horizon. Numerical results relating to the comparison of the performance of this hierarchical policy with the branch-and-bound scheme are presented.