Article ID: | iaor20071755 |
Country: | United Kingdom |
Volume: | 12 |
Issue: | 2 |
Start Page Number: | 215 |
End Page Number: | 234 |
Publication Date: | Mar 2005 |
Journal: | International Transactions in Operational Research |
Authors: | Chou Fuh-Der, Lee Ching-En, Chang Tzu-Yun |
Keywords: | heuristics |
This paper attempts to solve a single machine-scheduling problem, in which the objective function is to minimize the total weighted tardiness with different release dates of jobs. To address this scheduling problem, a heuristic scheduling algorithm is presented. A mathematical programming formulation is also formulated to validate the performance of the heuristic scheduling algorithm proposed herein. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. Overall, this algorithm can find the optimal solutions for 2200 out of 2400 randomly generated problems (91.67%). For the most complicated 20 job cases, it requires less than 0.0016 s to obtain an ultimate or even optimal solution. This heuristic scheduling algorithm can therefore efficiently solve this kind of problem.