Efficient Algorithms to Solve Tricriteria Machine Scheduling Problem

Abstract

The multicriteria single machine model is presented in this paper. We consider the machine scheduling problem (MSP) of n jobs on a single machine minimize a function of tricriteria: total completion time ( ), range of lateness ( ) and maximum tardiness ( ) which is an NP-hard problem. In the theoretical part of this work, we introduce the mathematical formulation of the discussed problem then demonstrate the importance of the dominance rule (DR) which can be applied in this problem to improve the good solutions. While in the practical part, one of the important exact methods; Branch and Bound (BAB) algorithm is applied to solve the suggested MSP tricriteria by finding a set of efficient solutions for up to n=18 jobs and BAB algorithm with DR up to n=39 jobs in a reasonable time to find the efficient solutions for the problem. In addition, to find good approximate solutions, we suggest two heuristic methods to solve the problem. The practical experiments prove the good performance of the two suggested methods.