Minimizing the Weighted Number of Early and Tardy Jobs on Uniform Machines

Abstract

Scheduling to maximize the (weighted) number of Just-In-Time (JIT) jobs or minimize the (weighted) number of early and tardy jobs on uniform
parallel machines are considered in this paper. The mathematical model formulation for the general case is presented. It is known that these problems are NP Complete on a single machine; this suggests that no efficient optimal solution seeking algorithms can obtain solution at polynomial time as the problem size increases. Two greedy based heuristic algorithms are proposed for solving the problem with a numerical example to illustrate it use. Extensive computational experiments performed with the heuristic on large scale problem sizes showed promising results.