برنامه ریزی موازی و ماشین آلات نامرتبط با اثرات زوال و بدتر شدن فعالیت های چند منظوره نگهداری برای به حداقل رساندن مجموع مدت زمان کل

This paper investigates scheduling problems with simultaneous considerations of deterioration effects and deteriorating multi-maintenance activities on unrelated parallel machines. We examine two models of scheduling with the deterioration effect, namely the job-dependent and position-dependent deterioration model and the time-dependent deterioration model. We assume that each machine may be subject to several maintenance activities over the scheduling horizon, and the duration of maintenance on a machine depends on its running time. Moreover, due to the restriction of the budget of maintenance, the upper bound of the total maintenance frequencies on all the machines is assumed to be known in advance. The objective is to find jointly the optimal maintenance frequencies, the optimal maintenance positions, and the optimal job sequences such that the total completion time is minimized. If the number of machines is fixed, we introduce polynomial time solutions for all the versions of the problem under study.

In typical scheduling problems, the processing times are assumed to be independent and constant. However, in many real-life situations, such as maintenance scheduling, cleaning assignments, steel production, and fire fighting, any delay in tackling a task may result in an increasing effort to perform the task. This phenomenon is known as the time-dependent deterioration effect in the literature. In scheduling with the time-dependent deterioration effect, the actual processing time of a job is an increasing function of its starting time. The recent paper by Janiak and Kovalyov [1] and the recent book by Gawiejnowicz [2] provided extensive reviews on this subject. On the other hand, the actual processing time of a job may vary depending on its scheduled position in a job sequence. For example, because of blunting of a cutting tool, the processing time required to process products may increase with respect to the number of products already processed. In scheduling with the position-dependent deterioration effect, the time required to perform a task increases with an increase of its position in the processing sequence. For details on this stream of research, the reader may refer to survey by Janiak and Rudek [3]. In addition, for research results on other scheduling models with deterioration effects and under different machine environments, a reader can refer to [4], [5], [6], [7], [8] and [9]. Most literature in scheduling problems assumes that the machines are continuously available over the scheduling horizon. However, this assumption is inappropriate in many practical situations. For example, a machine may not be available during the scheduling horizon due to maintenance activities, tool changes, or breakdowns. These impose a constraint on the machine availability for production. Scheduling under such environment is known as scheduling with availability constraints. It is well-known that the maintenance activity is important to improve the production efficiency of the machines or the quality of the products. During the maintenance activity, the machine is unavailable for processing jobs. Plentiful research has been conducted to address the maintenance activity in scheduling under different machine environments. For details on this stream of research, the reader may refer to the comprehensive surveys by Schmidt [10] and Ma et al. [11]. Moreover, in order to model a more realistic production system, the problem of joint scheduling with the deterioration effect and maintenance activity has received the attention of many researchers, including Wu and Lee [12], Ji et al. [13], Lee and Wu [14], Low et al. [15], Lodree and Geiger [16], Gawiejnowicz and Kononov [17], and Yang and Yang [18]. All the references mentioned above, which considered scheduling with the deterioration effect and the maintenance activity simultaneously, assumed that at most one maintenance activity is undertaken on each machine throughout the scheduling horizon. Nevertheless, in a real production setting, a machine may need multiple maintenance activities to improve its production efficiency. Therefore, a more realistic scheduling model should take into consideration associated multiple maintenance activities for a machine. Several recent studies have been done on scheduling with simultaneous considerations of the deterioration effects and multi-maintenance activities. Gawiejnowicz [19] considered two single-machine problems of scheduling a set of independent, non-preemptive and proportionally deteriorating jobs with constraints on availability of the machine or jobs. In both problems the criterion of schedule optimality is the maximum completion time. He proved that decision versions of these problems are NP-complete, but they were not shown to be strongly NP-hard [20]. Kuo and Yang [21] investigated a single-machine scheduling with a cyclic process of position-dependent deterioration effects and multi-maintenance activities where the objective is to minimize the makespan. They proposed a polynomial time algorithm to solve the problem. Zhao and Tang [22] extended the study of Kuo and Yang [21] to the case with the power position-dependent deterioration effects. They showed that the problem remains polynomially solvable. Yang and Yang [23] study a single-machine scheduling with the power position-dependent deterioration effects under multi-maintenance activities and variable maintenance duration considerations simultaneously to minimize the makespan. They showed that all the studied problems remain polynomially solvable. Yang and Yang [24] extended their study [23] to the objective of the total completion time minimization problem. They showed that the problem remains polynomially solvable if the upper bound on the maintenance frequency is given. To the best of our knowledge, very little study has been undertaken on the scheduling with simultaneous considerations of the deterioration effects and multi-maintenance activities on parallel machines. Yang [25] considered identical parallel-machine scheduling problems with simultaneous considerations of position-dependent deterioration effects and maintenance activities. The maintenance duration is considered to be a constant. The objective is to find jointly the optimal maintenance positions and the optimal job sequences to minimize the total machine load. He provided polynomial time solutions for all the problems studied. Yang et al. [26] studied the unrelated parallel-machine scheduling problem with position-dependent deterioration effects and multi-maintenance activities simultaneously. The maintenance duration is assumed to be a constant. They developed an efficient algorithm to minimize the total machine load when the maintenance frequencies on the machines are given. Furthermore, most research on scheduling with the maintenance activity regarded the maintenance duration constant no matter what conditions of the machine are. Nevertheless, in the real production settings, the machine maintenance duration may depend on its running time. That is, the later the maintenance activity is started, the worse the machine conditions are, and a longer time is needed to maintain it. This kind of maintenance can be considered as a deteriorating maintenance activity. Several recent papers have been conducted to address the deteriorating maintenance activity on scheduling problems [23], [24], [27], [28] and [29]. The motivation for this study stems from the metal or wood cutting process that cuts products to various sizes and shapes in a parallel-machine setting. The time required for processing a product depends on the quality of the cutting tool. Due to blunting, the actual processing time of a product increases with respect to the number of products already processed or the sum of the processing time of products already processed by the cutting tool. To counteract the blunting on a cutting tool, the maintenance activity may be performed on the cutting tool to sustain its production efficiency. In a normal situation, the cutting tool is maintained by an operator after it executes some products. In this situation, after the maintenance, the cutting tool reverts to its initial condition and the deterioration effect resumes as well. In addition, a cutting tool may need to maintain more than once to improve its production efficiency. Therefore, a more realistic machine scheduling model should take multiple maintenance activities into consideration. On the other hand, the maintenance duration of a cutting tool may depend on its running time. Consequently, in this study we consider scheduling with deterioration effects and deteriorating multi-maintenance activities simultaneously on an unrelated parallel-machine setting. The maintenance duration on a machine is assumed to be proportional to its running time between two consecutive maintenance activities on the machine. The objective is to find jointly the optimal maintenance frequencies, the optimal maintenance positions, and the optimal job sequences to minimize the total completion time. The remainder of this paper is organized as follows: In the next section we define the notation used in this study. In Section 3 we formulate the problem under study. In Section 4 we provide polynomial time solutions for variants of the problem. In Section 5 we present solutions to some special cases of the problem. In Section 6 we give a numerical example for solving the problem. We conclude the paper and suggest some topics for future research in the last section.

In this paper we investigated unrelated parallel-machine scheduling problems simultaneously with deterioration effects and deteriorating multi-maintenance activities. The aim was to find jointly the optimal maintenance frequencies, the optimal maintenance positions, and the optimal job sequences to minimize the total completion time when the upper bound of the total maintenance frequencies on all the machines is given (i.e., k is a given parameter). If the number of machines m was a given constant, we proposed polynomial time solutions for variants of the problem and some of its special cases. Further research may investigate problems concerning other models of maintenance duration, under other shop environments, and optimizing other performance measures.