ఇంటర్నేషనల్ జర్నల్ ఆఫ్ అడ్వాన్స్మెంట్స్ ఇన్ టెక్నాలజీ
అందరికి ప్రవేశం

నైరూప్య

Minimizing Makespan on Single Machine with Release Dates

E. O. Oyetunji, A. E. Oluleye

This paper considers the single criterion scheduling problem of minimizing makespan on a single machine with release dates. The problem is, by nature, NP-Hard, hence approximation algorithms are desired in order to solve the problem. An algorithm (called NAL) is proposed for the problem. The NAL algorithm is compared with the branch and bound (BB) method and a test algorithm (AEO) selected from the literature. The three solution methods were tested on a set of randomly generated problems (ranging from 10 to 500 jobs). Experimental results show that the proposed algorithm performed competitively with the BB method and outperformed the AEO algorithm.