In this research, we consider the problem of scheduling simultaneously tasks and operators in a workshop composed of identical parallel machines. We consider that the number of operators in the workshop is less than the number of machines. As a result, it may happen that an operator has to supervise simultaneously several machines. The productivity of each machine can thus be affected. We propose a model that describes the processing time modifications due to the shortage of operators to intervene on the machines. We assume that this deterioration is independent on the tasks being processed. On the other hand, we consider that if an operator handles several machines simultaneously, he could do so in different ways by giving different priorities to those machines. The working modes of operators may change over time. We therefore consider three types of changing viz. calendar ( i.e. the length of a working mode is a multiple of a given period), free, and at the end of a task. The problem consists then of determining intervals of time in which to utilize the different working modes in order to build a schedule that minimizes the total completion time (makespan).;For the free changing mode, we first start by proposing some mathematical properties characterizing the optimal solution, with regard to the makespan, in the case of two machines and one operator. Thereafter, we propose a graphical representation of the problem and present some mathematical properties deduced from this representation, in the case of two and three machines. Finally, we solve the problem by the heuristic approach. The results produced by a simulation show a very good performance of the heuristic utilized. The generated solutions are quasi-optimal from 20 tasks onwards. From 10 tasks onwards over 70% of the generated solutions have a makespan equal to the lower bound.;In the case where the operators working modes may only change at the end of a task, we consider the general case and two particular cases: the case where the assignment of the tasks to the machines is known and the case where the scheduling of the tasks on the machines is known. In the general case, i.e., where the assignments of the tasks to the machines and the operators working modes are not known a priori, we present five heuristic algorithms to solve the problem, and, for the case of two machines, the worst-case analysis for two of these heuristics. A simulation study is also undertaken to evaluate the average performance of these heuristics. From the results we obtained, we mainly conclude that the heuristics are efficient and their performance is interesting when the number of tasks gets larger. Furthermore, one of the heuristics dominates all others from 50 tasks. For each particular case, we present three heuristic algorithms to find the makespan, and carry out an experimental study to evaluate their performance in the average case. In each case, two heuristics are efficient and one of them dominates the others.;For the calendar changing mode, we consider three situations: the assignment of tasks is known, the working modes of the operators are known, and finally the (general) case where we do not have this information a priori . In the first case, we develop three heuristic algorithms, and undertake an experimental simulation to evaluate their performance in the average case. Throughout these experiments, we conclude that the best solutions are produced when the partitions are balanced. In the second case, we present another heuristic algorithm for which we undertake a worst-case analysis. A performance ratio of 1 + m-1n is obtained. In the third case, we present another heuristic involving a heuristic algorithm of the first case, and undertake an experimental study to evaluate its performance in the average case. The results produced by this study show a good performance of the heuristic when the number of tasks gets larger.
展开▼
