Comparison of Approximation Algorithms for Unrelated Parallel Machines to Minimize the Weighted Makespan

Abstract

The problem of scheduling of unrelated parallel machines is considered. In this environment, a set of n jobs has to be scheduled on m unrelated parallel machines. Each job is available for processing at time zero and each machine can process at most one job at a time and a job can be processed by at most one machine at a time. A case study is considered to schedule jobs in a cutting workshop to minimize the weighted makespan. Five algorithms are proposed and their performance is studied