Title: Finding Pareto optima for maximum tardiness, maximum earliness and number of tardy jobs

Authors: Ghasem Moslehi; Majid Rohani

Addresses: Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan 84156-83111, Iran ' Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan 84156-83111, Iran

Abstract: 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||Σ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.

Keywords: tardy jobs; maximum earliness; maximum tardiness; Pareto optima; branch and bound; just-in-time; JIT; multi-objective scheduling; single-machine scheduling.

DOI: 10.1504/IJOR.2012.047514

International Journal of Operational Research, 2012 Vol.14 No.4, pp.433 - 452

Published online: 11 Jan 2015 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article