Subscribe to our Newsletter and get informed about new publication regulary and special discounts for subscribers!

BSMaSS > Volume 1 > Common Due-Date Assignment and Job Scheduling on...
< Back to Volume

Common Due-Date Assignment and Job Scheduling on Single Machine and Parallel Machines

Full Text PDF


In this paper we consider a total penalty for the n job, one machine scheduling problem in which all jobs have a common due date. This penalty function is based on the due date value and on the earliness or the lateness of each job in the selected sequence. The main objective is to determine the optimal value of this due date and an optimal sequence to minimize a total penalty function. We prove that the optimal due date result can be generalized to the parallel machine problem. The problem of simultaneously available jobs on several parallel and identical machines. The problem is to find the optimal due date, assuming this to be the same for all jobs and we present a simple heuristic to find an approximate solution. On the basis of a limited experiment, we observe that the heuristic is very effective solution.


The Bulletin of Society for Mathematical Services and Standards (Volume 1)
J. K. Mane and K. P. Ghadle, "Common Due-Date Assignment and Job Scheduling on Single Machine and Parallel Machines", The Bulletin of Society for Mathematical Services and Standards, Vol. 1, pp. 6-13, 2012
Online since:
March 2012

BAKER, K. R. 1974. Introduction to Sequencing and Scheduling. John Wiley & Sons, New York.

BAKER, K. R., AND J. W. M. BERTRAND. 1980. A Comparison of Due-Date Selection Rules, Industrial Engr. Report 1980/02, University of Technology, Eindhoven, The Netherlands.

R. W. CONWAY, W. L. MAXWELL and L. W. MILLER (1967) Theory of Scheduling. Addison-Wesley, Reading, Mass.

A. H. G. RiNNooy KAN (1976) Machine Scheduling Problems: Classification, Complexity and Computations. Martinus Nijhoff, The Hague.

S. FRENCH (1 982) Sequencing and Scheduling Ellis Horwood, Chichester.

S. S. PANWALKAR, M. L. SMITH and A. SEIDMANN (1982) Common due-date assignment to minimize total penalty for the one machine scheduling problem. Opns Res. 30, 391-399.

EILON S. AND I. J. CHOWDHURY. 1976. Due-Dates in Job Shop Scheduling. Int. J. Prod. Res. 14, 223-237.

JONES, C. H. 1973. An Economic Evaluation of Job Shop Dispatching Rules. Mgmt. Sci. 20, 293-307.

WEEKS, J. K. 1979. A Simulation Study of Predictable Due-Dates. Mgmt. Sci. 25, 363-373.

WEEKS, J. K., AND J. S. FRYER. 1977. A Methodology for Assigning Minimum CostDueDates. Mgmt. Sci. 23, 872-881.

HALL, N. 1986. Single and Multi-Processor Models for Minimizing Completion TimeVariance. Navai. Res. Logist. Quart. 33, 49-54.

SUNDARARAGHAVAN, P., AND M. AHED. 1984. Minimizing the Sum of AbsoluteLateness in Single Machine and Multimachine Scheduling. Navai. Res. Logist. Quart. 31, 325-333.

Show More Hide