Ordered minimum completion time heuristic for unrelated parallel-machines problems

Scheduling problems in parallel machines have been deeply studied and many are too complex to be solved by exact methods. The unrelated parallel machines makespan minimization problem (Rm||Cmax) is known to be NP-hard and is usually solved using heuristics. Considering heuristics used in these problems, it is possible to identify two different approaches, those that use the execution time to allocate tasks and those that use the completion time. This paper proposes a new heuristic, OMCT (Ordered Minimum Completion Time), based on the performance limitation of the MCT (Minimum Completion Time). The computational study results demonstrate the effectiveness of the proposed heuristic.