A common due-date assignment problem on parallel identical machines

We address a job scheduling and due-date assignment problem on parallel identical machines. All jobs share a common due-date, which is to be determined. The cost of a given schedule is a function of the maximum earliness cost, the maximum tardiness cost, and the due-date cost. The objective is of a minimax type, i.e. we look for the schedule and due-date with minimum cost of the worst scheduled job. We focus on the introduction of an efficient heuristic algorithm for this NP-hard problem. We then introduce an easily obtained lower bound on the optimal cost. The heuristic (lower bound) is shown to be asymptotically optimal (accurate) under very general assumptions. Both the heuristic and the lower bound are shown to perform extremely well in our extensive numerical study. For example, the average optimality gap of all problems with 100 jobs on three machines is about 0.0006. Both the heuristic and the lower bound are extended to allow for general monotone cost functions. We also study the special case of identical processing times for all jobs, which is shown to be polynomially solvable even for general monotone costs.