Journal of Emerging Trends in Engineering and Applied Sciences: Research Areas

Article Title: Minimizing Makespan and Total Completion Time Criteria on a Single Machine with Release Dates
by E. O. Oyetunji and A. E. Oluleye

Abstract:
This paper considers the scheduling problem of simultaneously minimizing the makespan and total completion time criteria on a single machine with release dates. Since the problem has been characterized as NP-Hard, approximation algorithms are desired for solving the problem. A new implementation of an existing algorithm (GAlg) was adopted for this scheduling problem. This is appropriately named NGAlg algorithm. The NGAlg algorithm was compared with the Best Beta (BESTB) algorithm selected from the literature. The two criteria were aggregated together into a linear composite objective function (LCOF). Five variants of the LCOF were utilized. Performance evaluations were based on both effectiveness and efficiency of the algorithms. Both NGAlg and BESTB algorithms were tested on a set of 900 randomly generated single machine scheduling problems. Experimental results show that the NGAlg algorithm outperformed the BESTB algorithm under all the five different LCOFs and the considered problem sizes.

Keywords: criteria, algorithm, single machine, dimensionless, makespan, total completion time

Download full paper