Optimal idle time insertion in early-tardy parallel machines scheduling with precedence constraints

Consider a set of n jobs to be processed on a set of μ unrelated parallel machines subject to precedence constraints, where the objective is to minimize the sum of earliness and tardiness penalties. In minimizing this non-regular performance measure, it is necessary to assign jobs to machines, determine the sequence on each machine and possibly insert intentional idle times between jobs. Here, this third aspect is considered assuming that the assignment of jobs to machines and the sequence on each machine are known. This idle time insertion problem, though polynomially solvable, is not a trivial task, since it requires the consideration of all machines simultaneously when precedence constraints among jobs are present. It can also be seen as the problem of optimally timing a partially ordered set of tasks with respect to the above non-regular performance measure. An exact procedure is proposed based on repeated solutions of maximum cardinality matching problems on a bipartite graph with O(mn) complexity where m < μ · n is the total number of non-redundant arcs of the digraph induced by the precedence relationships. Computational results are provided.