இன்டர்நேஷனல் ஜர்னல் ஆஃப் அட்வான்ஸ்மென்ட்ஸ் இன் டெக்னாலஜி
திறந்த அணுகல்

சுருக்கம்

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.