Minimization of earliness, tardiness and due date penalties on uniform parallel machines with identical jobs

We consider a problem of scheduling n identical nonpreemptive jobs with a common due date on m uniform parallel machines. The objective is to determine an optimal value of the due date and an optimal allocation of jobs onto machines so as to minimize a total cost function, which is the function of earliness, tardiness and due date values. For the problem under study, we establish a set of properties of an optimal solution and suggest a two-phase algorithm to tackle the problem. First, we limit the number of due dates one needs to consider in pursuit of optimality. Next, we provide a polynomial-time algorithm to build an optimal schedule for a fixed due date. The key result is an O(m2 log m) algorithm that solves the main problem to optimality.Scope and purpose: To extend the existing research on cost minimization with earliness, tardiness and due date penalties to the case of uniform parallel machines.

► n identical nonpreemptive jobs are scheduled on m uniform parallel machines.
► There is a common due date for all jobs.
► The objective is to minimize total earliness, tardiness and due date costs.
► The fixed due date version of the problem is solved in O(m log m) time.
► If the common due date is to be determined the problem is solved in O(m2 log m) time.