Sequence Jobs and Assign Due Dates with Uncertain Processing Times and Quadratic Penalty Functions

摘要

This paper considers due date assignment and sequencing for multiple jobs in a single machine shop. The processing time of each job is assumed to be uncertain and is characterized by a mean and a variance with no knowledge of the entire distribution. The objective is to minimize the combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. The earliness and tardiness penalties and the penalty associated with long due date assignment are all expressed quadratic functions. Heuristic procedures are developed for the objective function. The due dates and sequences obtained by these procedures depend not only on means but also variances of the job processing times. Our numerical examples indicate that the variance information of job processing times can be useful for sequencing and due date assignment decisions. In addition, the performance of the procedures proposed in this paper are robust and stable with respect to job processing time distributions.