An ordered heuristic for the allocation of resources in unrelated parallel-machines

Abstract

All rights reserved. Global competition pressures have forced manufactures to adapt their productive capabilities. In order to satisfy the ever-changing market demands many organizations adopted flexible resources capable of executing several products with different performance criteria. The unrelated parallel-machines makespan minimization problem (Rm||Cmax) is known to be NP-hard or too complex to be solved exactly. In the heuristics used for this problem, the MCT (Minimum Completion Time), which is the base for several others, allocates tasks in a random like order to the minimum completion time machine. This paper proposes an ordered approach to the MCT heuristic. MOMCT (Modified Ordered Minimum Completion Time) will order tasks in accordance to the MS index, which represents the mean difference of the completion time on each machine and the one on the minimum completion time machine. The computational study demonstrates the improved performance of MOMCT over the MCT heuristic.