A heuristic algorithm to minimize total weighted tardiness on a single machine with release times

A heuristic algorithm to minimize total weighted tardiness on a single machine with release times

0.00 Avg rating0 Votes
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: , ,
Keywords: heuristics
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.