text: This chapter presents a novel idea for the general case of the Common Due-Date (CDD) scheduling problem. The problem is about scheduling a certain number of jobs on a single or parallel machines where all the jobs possess different processing times but a common due-date. The objective of the problem is to minimize the total penalty incurred due to earliness or tardiness of the job completions. This work presents exact polynomial algorithms for optimizing a given job sequence for single and identical parallel machines with the run-time complexities of O(nlogn) for both cases, where n is the number of jobs. Besides, we show that our approach for the parallel machine case is also suitable for non-identical parallel machines. We prove the optimality for the single machine case and the run-time complexities of both. Henceforth, we extend our approach to one particular dynamic case of the CDD and conclude the chapter with our results for the benchmark instances provided in the OR library.
  @cite_0: Given processing times of n jobs on a single machine with penalties for earliness and tardiness and penalties associated with assignment of due-dates, the objective is to select optimal due-dates and optimal sequence. Scheduling procedure for the solution of this problem is presented along with proof of optimality and illustrative numerical examples.
  @cite_5: We consider an n job, one machine scheduling problem in which all jobs have a common due date. The objective is to determine the optimal value of this due date and an optimal sequence to minimize a total penalty function. This penalty function is based on the due date value and on the earliness or the lateness of each job in the selected sequence. We present a polynomial bound scheduling algorithm for the solution of this problem along with the proof of optimality, a numerical example and discuss some extensions.
  @cite_16: This paper considers a single-machine scheduling problem in which penalities occur when a job is completed early or late. The objective is to minimize the total penalty subject to restrictive assumptions on the due dates and penalty functions for jobs. A procedure is presented for finding an optimal schedule.
summary: The Common due-date problem has been studied extensively during the last @math years with several variants and special cases @cite_0 @cite_16 . In @math , Kanet presented an O( @math ) algorithm for minimizing the total absolute deviation of the completion of jobs from the due date for the single machine, @math being the number of jobs @cite_16 . Panwalkar considered the problem of common due-date assignment to minimize the total penalty for one machine @cite_5 . The objective of the problem was to determine the optimum value for the due-date and the optimal job sequence to minimize the penalty function, where the penalty function also depends on the due-date along with earliness and tardiness. An algorithm of O( @math ) complexity was presented but the special problem considered by them consisted of symmetric costs for all the jobs @cite_0 @cite_5 .