Parallel machine scheduling to minimize costs for earliness and number of tardy jobs (Q1315994)

This paper discusses problems of scheduling \(n\) independent jobs on \(m\) identical parallel machines so as to minimize costs for earliness, due date assignment and weighted number of tardy jobs. The main complexity result is as follows: (1) The single machine problem with an adjustable common due date is solvable in \(O(n\log n)\) time if tardiness penalties \(w\) are equal, earliness cost \(f\) and due date assignment cost \(g\) are arbitrary, solvable in \(O(n^ 4)\) time if \(w\) is different, and \(f\) and \(g\) are linear, but NP-hard if one of \(f\) and \(g\) is arbitrary. (2) The single machine problem with an externally given common due date is solvable if machine idle time are allowed, but is open if machine idle times are forbidden. (3) The multiple machine problem with an adjustable common due date is NP-hard except \(g= 0\) and \(f\) is linear (or \(g\) is linear and \(f= 0\)).