A heuristic approach to minimize three criteria using efficient solutions

Abstract

In optimization, scheduling problems is concerning allocations of some resources which are usually limited. These allocations are done in order to fulfil some criterion by performing some tasks or jobs to optimize one or more objective functions. Simultaneous multi-criteria scheduling problem is known as np-hard optimization problem. Here, we consider three criteria for scheduling a number of jobs on a single machine. The problem is to minimize the sum of total completion time, maximum earliness and maximum tardiness. Every job is to be processed without interruption and becomes available for processing at time zero. The aim is to find a processing order of the jobs to minimize three-objective functions simultaneously. We present a new heuristic approach to find a best overall solution (accepted) of the problem using efficient solutions of one of the other related criteria. We establish a result to restrict the range of the optimal solution, and the lower bound depends on the decomposition of the problem into three subproblems. The approach is tested on a set of problems of different number of jobs. Computational results demonstrate the efficiency of the proposed approach.