The paper discusses the one-machine-model with deterministic processing times. In the first part it restricts the model to the common due date case. In the second part an equivalence between this model and the ‘Equal Slack Due Date’ model is shown. As a penalty function F the paper uses the sum of identical functions f of the lateness (both earliness and tardiness). The function f must be monotonous with respect to the absolute lateness. No other restrictions are necessary. Several special cases are known in the literature and summarized here to show the generality of our approach. This idea of penalizing jobs whose completion times deviate from their due date arises in some scheduling models for ‘just-in-time’ production. The paper gives two structural results for an optimal schedule: An optimal schedule works without idle times except eventually one at time 0 and is ‘v-shaped’. Using these two structural results it constructs an optimal schedule with a pseudopolynomial algorithm. This algorithm has a complexity bound of O(nP), where P denotes the sum of the given processing times. For a subclass of penalty functions, the paper extends the pseudopolynomial algorithm to a fully polynomial approximation scheme. The complexity bound for this approximation scheme is of the order O(n3ë(1/∈)), where ∈ denotes the relative precision of the approximate solution. As mentioned above the paper shows the equivalence of the ‘common due date’ problem and the ‘equal slack due date’ problem. Mathematically these two problems can be expressed as: Common Due Date Rule: d(i):¸=d for all jobs i, and Equal Slack Rule: d(i):¸=d+p(i) for all jobs i, where p(i) denotes the given processing time of job i and d is a constant value.
