Finding Pareto optima for maximum tardiness, maximum earliness and number of tardy jobs (Q2627310)

Summary: Just-in-time JIT (Just In Time) is an important procedure in scheduling problems which aims at minimizing minimising both earliness and tardiness at the same time. In this case, the problem is a multi-objective scheduling problem. A candidate solution method for this type of problem is finding the Pareto-optima. The present research investigates the single-machine scheduling problem in which the three objects: number of tardy job, maximum earliness, and maximum tardiness must be minimized minimised \((1\|\sum U_j,E_{\max},T_{\max})\). The branch and bound approach is proposed to find the Pareto-optima. A number of new dominance properties, upper bound, and lower bound rules are developed that help the branch and bound procedure to perform more efficiently. We generate 700 random problems to test our approach. Computational results are reported, for instances, of up to 30 jobs in size.