A HEURISTIC ALGORITHM TO MINIMIZE TOTAL WEIGHTED TARDINESS ON A SINGLE MACHINE WITH RELEASE DATES AND SEQUENCE-DEPENDENT SETUP TIMES

Abstract

This paper attempts to solve a single machine scheduling problem (n|l|r(subscript i), s(subscript ij)|∑w(subscript i)T(subscript i)), in which the objective function is to minimize the total weighted tardiness with different release dates and sequence-dependent setup times. There is not a mathematical programming or a heuristic method for this type of problem up to now. In this study, we propose a heuristic scheduling algorithm with the complexity of O(n^3)to solve this problem. To validate the performance of the heuristic proposed herein, a mathematical programming with logical constraints model is also formulated. Experimental results show that this algorithm can find10321 optimal solutions out of 12600 randomly generated problems. Total average solution quality is 98.03%. A11-Job case(large problem)requires only 0.00065 seconds, on average, to obtain an ultimate solution. The results demonstrate that the heuristic scheduling algorithm can efficiently solve this kind of problem.