Due-Date Scheduling

New production technologies like “just-in-time” production lead to special scheduling problems involving due dates d _i . Contrary to classical scheduling problems where the objective function simply involves lateness L _i = C _i − d _i or tardiness T _i = max{0, C _i − d _i } penalties, earliness E _i = max{0, d _i − C _i } is now also of importance. Objective functions such as Σ w _i | L _i | and Σ w _i L _i 2 are typical of “just-in-time” situations. Note that L _i = T _i + E _i and L _i 2 = T _i 2 + E _i 2. From the practical and theoretical point of view, situations in which all due dates are equal are of importance. This due date d may be a given parameter of the problem or it may be a variable, i.e. we are interested in an optimal due date d _opt with respect to the objective function. To indicate these special situations we add d or d _opt to the job characteristics of the problem. If the due date is a variable, then we may add due-date assignment costs w _d · d to the objective function.