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_13: Abstract This paper considers due-date assignments and sequencing of n jobs in a single- machine shop in which each job is given a constant waiting allowance. The objective is to find the optimal value of the waiting allowance and the optimal job sequence to minimize a cost function based on the waiting allowance and the job earliness and tardiness values. We formulate the problem as an LP and find the optimal solution via considering the LP dual problem and show that the optimal waiting allowance is independent of the job sequence.
  @cite_18: This article uses tabu search to solve the restricted, common-due-date, early tardy machine scheduling problem generalised earliness and tardiness penalties. Different forms of the tabu search are tested, including one based on a sequence of jobs solution space and another based on an early tardy solution space. Results show that a search which uses an early tardy solution space with a neighbourhood scheme which eliminates infeasible areas of the solution space is the most efficient and effective solution method.
  @cite_1: A companion paper Part I considers the problem of minimizing the weighted earliness and tardiness of jobs scheduled on a single machine around a common due date, d, which is unrestrictively late. This paper Part II considers the problem of minimizing the unweighted earliness and tardiness of jobs, allowing the possibility that d is early enough to constrain the scheduling decision. We describe several optimality conditions. The recognition version of the problem is shown to be NP-complete in the ordinary sense, confirming a well known conjecture. Moreover, this complexity definition is precise, since we describe a dynamic programming algorithm which runs in pseudopolynomial time. This algorithm is also extremely efficient computationally, providing an improvement over earlier procedures, of almost two orders of magnitude in the size of instance that can be solved. Finally, we describe a special case of the problem which is polynomially solvable.
  @cite_2: A set of n jobs has to be scheduled on a single machine which can handle only one job at a time. Each job requires a given positive uninterrupted processing time and has a positive weight. The problem is to find a schedule that minimizes the sum of weighted deviations of the job completion times from a given common due date d, which is smaller than the sum of the processing times. We prove that this problem is NP-hard even if all job weights are equal. In addition, we present a pseudopolynomial algorithm that requires O(n2d) time and O(nd) space.
  @cite_10: We consider a one-machine scheduling problem with earliness and tardiness penalties. All jobs are assigned a common due date and the objective is to minimize the total penalty due to job earliness and tardiness. We are interested in finding the optimal combination of the common due-date value and the job sequence. Despite the fact that this problem in general is very hard to solve, we prove that there exists at least a common property for all optimal solutions: The first job in an optimal sequence is one of the longest jobs. We also prove that this property holds for a general class of unimodal penalty functions.
summary: Cheng again considered the same problem with slight variations and presented a linear programming formulation @cite_13 . In @math Cheng and Kahlbacher and Hall studied the CDD problem extensively, presenting some useful properties for the general case @cite_10 @cite_1 . A pseudo polynomial algorithm of O( @math ) (where, @math is the common due-date) complexity was presented by Hoogeveen and Van de Velde for the restrictive case with one machine when the earliness and tardiness penalty weights are symmetric for all the jobs @cite_2 . In @math Hall studied the unweighted earliness and tardiness problem and presented a dynamic programming algorithm @cite_1 . Besides these earlier works, there has been some research on heuristic algorithms for the general common due date problem with asymmetric penalty costs. James presented a tabu search algorithm for the general case of the problem in @math @cite_18 .