Due date assignment in single machine with stochastic processing times

Abstract

This paper considers two different due date assignment and sequencing problems in single machine where the processing times of jobs are random variables. The first problem is to minimise the maximum due date so that all jobs are stochastically on time. It is shown that sequencing the jobs in decreasing service level (DSL) order optimally solves the problem. The results are then extended for two special cases of flow shop problem. The other problem is to minimise a total cost function which is a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. The assignment of a common due date and distinct due dates are investigated for this problem. It is shown that the optimal sequence for the case of common due date is V-shaped.

Keywords:

• due date assignment
• earliness
• tardiness
• stochastic scheduling