Paper
New Approximation Algorithms for Minimizing Number of Tardy Jobs on Single Machine with Release Dates
- Authors:
- A. O. Akinrinde; E. O. Oyetunji; A. E. Oluleye
- Abstract
- This paper deals with the scheduling problem of minimizing number of tardy jobs on a single machine with release dates. The problem is considered as NP-Hard, because it is difficult to solve and no known polynomial bounded algorithm exist that guarantees optimal solution. Therefore, four approximation algorithms (JB1, JB2, JB3 and JB4) were proposed to solve the problem. The proposed algorithms were compared with two heuristics (DAU and EOO) that were proposed previously for this same problem. Twenty-two problem sizes ranging from three to five hundred jobs with fifty different simulated problems for each problem size, which gave one thousand, one hundred problems were solved. The four algorithms were coded using Microsoft visual basic 6.0 while statistica 8.0 was used to analyze the results. Performance evaluation was based on both effectiveness and efficiency. Experimental results were provided while appropriate recommendations were made.
- Keywords
- Scheduling; Single Machine; Tardy Jobs; Heuristic; Performance Ratio
- StartPage
- 211
- EndPage
- 220
- Doi