Premium
A heuristic algorithm to minimize total weighted tardiness on a single machine with release times
Author(s) -
Chou FuhDer,
Chang TzuYun,
Lee ChingEn
Publication year - 2005
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/j.1475-3995.2005.00499.x
Subject(s) - tardiness , mathematical optimization , computer science , scheduling (production processes) , single machine scheduling , job shop scheduling , algorithm , heuristic , null move heuristic , mathematics , schedule , operating system
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.