مسائل برنامه ریزی موازی ماشین آلات نامرتبط با در نظر گرفتن تاثیرات فرسودگی و فعالیت های تعمیر و نگهداری مخرب

This paper explores the problems of unrelated parallel-machine scheduling with aging effects and deteriorating maintenance activities. The jobs are non-resumable. Each machine has at most one maintenance activity which is allowed throughout the planning horizon. Assume that once the maintenance activity is completed, the functions of machine and the properties of jobs e.g. the temperature (hardness) of materials that processed by the machine will be restored to their initial conditions. The length of the maintenance activity is a linear function of its starting time. The objectives of this study are to minimize the total completion time and the total machine load. Three basic types of aging effect model are proposed. We show that all the proposed models can be solved optimally in polynomial time.

In deterministic scheduling, job-processing time is fixed throughout the whole process. However, there are many situations in which the processing time of jobs may be changed due to aging (deteriorating) and/or learning phenomena. Machine scheduling problems with aging and/or learning effect have been extensively studied during the past few decades in various machine settings and performance measures. Gupta and Gupta [10] and Browne and Yechiali [5] probably were the first researchers to introduce the deterioration effect into scheduling problems. Browne and Yechiali [5] presented an optimal solution for expected makespan minimization problem of single-machine scheduling under linear deteriorating conditions. Since then, numbers of plentiful research related to the deteriorating jobs have been conducted in scheduling under different machine environments. Bachman and Janiak [1] studied a scheduling problem for the deteriorating jobs with ready time to minimize the makespan. Bachman and Janiak [2] showed that the maximum lateness minimization problem under the linear deterioration assumption is NP-hard, and presented two heuristic algorithms. Bachman et al. [3] considered the problem of minimizing the total weighted completion time introduced by Browne and Yechiali [5]. They proved that problem is NP-hard. Ng et al. [26] studied three different decreasing linear functions of deterioration and showed that two of these problems could be solved in polynomial time and they presented a dynamic programming method for the third problem. Lee and Lai [22] proposed a general model with deteriorating jobs and learning effects where the actual processing time of a job is a general function of the normal processing time of the jobs already processed and its scheduled position. They showed that the problems to minimize the makespan, the total completion time, the sum of the power of the completion time are polynomially solvable. In addition, they showed that the total weighted completion time, the maximum lateness, the maximum tardiness, the total tardiness problems are polynomially solvable under a certain condition. Yin et al. [31] considered a scheduling environment with two agents and a linear non-increasing deterioration. Three different objective functions are considered for one agent, including the maximum earliness cost, total earliness cost and total weighted earliness cost, while keeping the maximum earliness cost of the other agent below or at a fixed level U. They presented the optimal properties and the complexity results for the proposed problems, respectively. Hsu et al. [11] studied the unrelated parallel-machine scheduling problem with rate-modifying activities to minimize the total completion time. They showed that the problem can be solved in polynomial time. Yin et al. [30] pointed out by a counterexample that the main results in a recent paper by Lee and Lai [22] are incorrect, and provided a sufficient condition for them being true. Kuo et al. [19] explored a time-dependent learning effect in a flowshop scheduling problem. For a complete list of studies, the reader may refer to the comprehensive survey by Janiak and Rudek [12] and [13], Janiak et al. [14], Cheng et al. [7] and Biskup [4], and a book of Gawiejnowicz [9]. Production scheduling and preventive maintenance planning are the most common and significant problems faced by the manufacturing industry. Such a problem is commonly known as machine scheduling with availability constraints. For the recent researches, Wu and Lee [29] studied a single-machine scheduling problem with an availability constraint under linear deteriorating jobs. They followed the assumption proposed by Browne and Yechiali [5]. To be brief, the resumable availability and processing time of a specific job based on its starting time throughout the planning horizon are considered in their paper. Gawiejnowicz [8] considered two problems of a single machine scheduling of independent, non-resumable and proportionally deteriorating jobs, with constraints on availability of the machine or of jobs and the maximum completion time criterion. He showed that decision versions of those problems are NP-complete in the ordinary sense or in the strong sense, depending on the number of non-availability periods or the number of distinct ready time and deadlines. Ji et al. [15] studied the same problem as Wu and Lee [29] proposed under the non-resumable case. Their objectives were to minimize the makespan and the total completion time. They proved that both problems are NP-hard and presented pseudo-polynomial time optimal algorithms to solve those problems. Lee and Wu [21] explored multi-machine scheduling with deteriorating jobs and scheduled maintenance. Both of the resumable and non-resumable cases were discussed with the objective of minimizing the makespan. A lower bound and an efficient heuristic algorithm were derived for each case. Low et al. [24] studied the same model as Ji et al. [15] argued under the aging effect assumption. They proved that problem was NP-hard and provided heuristic algorithm to solve it. Additionally, a good strategy of setting the maintenance to start epoch when half of jobs were processed was suggested as well. Kuo and Yang [18] studied a single-machine scheduling problem with the cyclic processes of an aging effect. They introduced polynomial time algorithm to minimize makespan. Lodree and Geiger [23] studied a sequence-independent, single processor makespan problem with position-dependent processing time and showed that under certain conditions, the optimal policy is to schedule the rate-modifying activity in the middle of the task sequence. All of the studies mentioned above assumed that the length of the maintenance activity is constant no matter what the machine condition is. Nevertheless, in the real production settings, the length of maintenance activity depends on the running time of machine. That is, the earlier the maintenance activity starts, the better the machine condition is, and the less time is needed to maintain it. Example can be found in the timber industry, the log band mills are one of the main machines in a sawmill. Generally, the saw of a log band mill is maintained by an auto band saw sharpener to sustain the sharpness of its teeth. Specifically, the earlier a log band mill undergoes the teeth sharpening maintenance activity, the less blunt its teeth are. Therefore, the less time is needed to sharpen them [11]. This kind of maintenance is specified as a deteriorating maintenance [25]. Kubzin and Strusevich [16] studied a two-machine flow shop scheduling problem with no-wait in process to minimize the completion time. They assumed that the length of maintenance period depended on its starting time and provided a polynomial time approximation scheme for the problem. Moreover, Kubzin and Strusevich [17] considered two-machine open shop and flow shop scheduling problems to minimize the maximum completion time, respectively. They assumed that each machine had to be maintained exactly once during the planning horizon and the length of each of maintenance interval depended on its starting time. They showed that the open shop is polynomially solvable and the flow shop problem is a NP-hard problem. They also presented a fully polynomial approximation scheme and a fast 3/2-approximation algorithm. Mosheiov and Sidney [25] studied single-machine scheduling problems with an option to perform a deteriorating maintenance activity. The objective functions are makespan, flowtime, maximum lateness, total earliness, tardiness and due-date cost, and number of tardy jobs. They introduced polynomial time solutions for all these problems. In the metal cutting process, due to the wear of the cutting tool, the actual processing time of a job on a machine increases due to the number of jobs that have already been processed [12]. The time required for processing a single product depends on the quality of the tool of cutting machine. That is, whether the cutting tool is new or just after some maintenance is critical. In a normal situation, the cutting machine is maintained by an operator after it executes some products. Therefore, after the maintenance, the cutting tool is reverted to its initial condition and the aging effect is resumed as well. The maintenance duration may depend on the running time of the cutting tool. The longer the maintenance is delayed, the worse the cutting tool condition is. So the maintenance requires more time and effort. The motivation for this study stems from a cutting machine that cuts various sizes and shapes of material. Each machine is operated by a skilled worker. Typically, several machines are simultaneously available and a job (a piece of material) can be processed by any one of them. Since the conditions of the cutting machine and workers are different, the jobs have different processing time depending on the cutting machines selected to process. Three types of aging effect model were conducted. We showed that all of the addressed models can be solved optimally in polynomial time.

This study explored the problems concerning unrelated parallel-machine scheduling with aging effects and deteriorating maintenance activities. For the addressed problems, three types of aging effect model were conducted. We showed that all of the proposed models could be solved optimally in polynomial time. Future research may focus on similar problems with several maintenance activities throughout the planning horizon. It would also be interesting to investigate an extension of the problems to other shops, or other performance measures.