Scheduling identical parallel machines and operators within a period based changing mode

This article addresses the problem of scheduling n non-preemptive jobs on m identical parallel machines with omega operators to minimize the makespan. The number of operators is less than the number of machines. As a result, it may happen that an operator has to supervise simultaneously several machines. This in turn has an impact on the job processing times as they become a function of the operators modus operandi. In this paper we consider the case where each modus operandi can only be changed at the end of a given period, i.e., a period based changing mode. We present heuristic algorithms to solve this problem. An experimental study is conducted to evaluate the performance of these heuristics in the average case, and a worst case analysis is presented for one of them. (C) 2009 Elsevier Ltd. All rights reserved.