Determination of an optimal common due date and optimal sequence in a single machine job shop

Abstract

In this paper we consider an n jobs one machine sequencing problem in which all jobs have a common due date and a deviation in its completion time occurs when a job is completed before or after the common due date. The objective is to find an optimal value of this common due date and a corresponding optimal sequence such that the mean absolute deviation of the completion times of the jobs in the optimal sequence from the corresponding optimal common due date is at its global minimum. Starting with an arbitrary sequence we relate the problem to a generalized linear goal program from which some basic results are proved using elementary properties of linear equations and a linear goal programming problem. Using these results and the idea of sensitivity analysis in linear programming, an algorithm is developed that determines the optimal due date and the corresponding optimal sequence yielding the global minimum value of the mean absolute deviation of the completion times of the jobs in the optimal sequence from the corresponding optimal common due date. In the end a numerical example to explain the algorithm is provided.