Minimization of squared deviation of completion times about a common due date

We discuss a non-preemptive single-machine job sequencing problem where the objective is to minimize the sum of squared deviation of completion times of jobs from a common due date. There are three versions of the problem—tightly restricted, restricted and unrestricted. Separate dynamic programming formulations have already been suggested for each of these versions, but no unified approach is available. We have proposed a pseudo-polynomial DP solution and a polynomial heuristic for general instance. Computational results show that tightly restricted instances of up to 600 jobs can be solved in less than 6 s. General instances of up to 80 jobs take less than 2 s.Statement of scope and purposeIn this paper, we have considered an NP-complete single-machine scheduling problem arising in JIT environment, a field of great importance in manufacturing industry. The objective of the problem is to schedule a set of given jobs to minimize the sum of squared deviation of their completion times from a common due date. This paper presents a number of precedence rules, a polynomial heuristic and more importantly a unified pseudo-polynomial dynamic programming formulation. Empirical results show that the dynamic programming formulation performs better than the existing approaches.