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

Maintenance is important to manufacturing process as it helps improve the efficiency of production. Although different models of joint deterioration and learning effects have been studied extensively in various areas, it has rarely been studied in the context of scheduling with maintenance activities. This paper considers scheduling with jointly the deterioration and learning effects and multi-maintenance activities on a single-machine setting. We assume that the machine may have several maintenance activities to improve its production efficiency during the scheduling horizon, and the duration of each maintenance activity depends on the running time of the machine. The objectives are to determine the optimal maintenance frequencies, the optimal maintenance locations, and the optimal job schedule such that the makespan and the total completion time are minimized, respectively, when the upper bound of the maintenance frequencies on the machine is known in advance. We show that all the problems studied can be solved by polynomial time algorithms.

There are many situations where the processing time of a job may be subject to change due to deterioration or learning phenomena. Many researchers have devoted to address the jobs deterioration or the learning effect in scheduling under different machine environments. For a complete list of studies, the jobs deterioration scheduling problems are discussed in a survey by Cheng, Ding, and Lin (2004) and a recent book by Gawiejnowicz (2008); while the learning effect scheduling problems are discussed in reviews by Bachman and Janiak, 2004, Biskup, 2008 and Janiak and Rudek, 2009. The phenomena of deterioration and learning occurring simultaneously can be found in many real-life situations (see, e.g., Wang, 2007). Scheduling problems with the jobs deterioration and the learning effect have been extensively studied in recent years. Lee (2004) was the pioneer to introduce the deterioration and learning effects simultaneously in scheduling problems. Since then, many researchers have devoted large amounts of effort to this relatively young but vivid area of scheduling research from a variety of perspectives. The reader can refer to recent papers by Wang, 2007, Wang and Cheng, 2007, Wang, 2009a, Wang, 2009b, Sun, 2009, Wang et al., 2009, Wang and Liu, 2009, Yang and Kuo, 2010, Huang et al., 2010 and Wang and Guo, 2010. On the other hand, machine maintenance is often undertaken in manufacturing system to prevent premature machine failures with a view to sustaining production efficiency. However, the maintenance activity disrupts machine availability for production because the machine during the maintenance activity is unavailable for processing jobs. Scheduling under such an environment is known as scheduling with availability constraints. The problem of joint scheduling and availability constraint has attracted the attention by many researchers. For details on this stream of research, the reader can refer to the comprehensive surveys by Schmidt, 2000 and Ma et al., 2010, among others. In addition, there has been growing interest in the literature to study scheduling problems with the jobs deterioration and the maintenance activity in recent years. Several studies have investigated this subject under different machine environments, which include Wu and Lee, 2003, Ji et al., 2006, Lee and Wu, 2008, Low et al., 2008, Lodree and Geiger, 2010 and Gawiejnowicz and Kononov, 2010. Most above mentioned references, which investigated scheduling problems with jointly the jobs deterioration and the maintenance activity, assumed that at most one maintenance activity is undertaken on a machine throughout the scheduling horizon. Nevertheless, in a real manufacturing process, a machine may require multi-maintenance activities to improve its production efficiency. Therefore, a more realistic machine scheduling model should take multi-maintenance activities into consideration. However, very little study has been done on this topic. Gawiejnowicz (2007) 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. Yang and Yang (2010a) investigated single-machine scheduling with jobs deterioration and maintenance activities to minimize the total completion time. They show that the problem remains polynomially solvable if the upper bound on the maintenance frequency is given. Furthermore, most research considered machine scheduling with the maintenance activity assumed that the maintenance duration is a constant no matter what the condition of the machine is. However, this assumption may be inappropriate in many practical manufacturing processes. The maintenance duration may depend on the running time of the machine, that is, the later maintenance activity is performed, the worse the machine conditions are, and a longer time is needed to perform the maintenance activity. This kind of maintenance activity can be considered as a deteriorating maintenance activity. Several recent papers have been conducted to address the deteriorating maintenance activity in scheduling problems (see Kubzin and Strusevich, 2005, Kubzin and Strusevich, 2006, Mosheiov and Sidney, 2010, Yang et al., 2010, Yang and Yang, 2010a and Yang and Yang, 2010b). To the best of our knowledge, however, scheduling with simultaneous considerations of the deterioration and learning effects and multi-maintenance activities has never been studied. The motivation for this study stems from the steel rolling mills. Before the manufacturing process, the ingot needs to preheat to the required temperature. Thus, the longer the ingot waits for the processing on the rolling machine, the lower the temperature drops and the longer the processing time needs (see Buzacott and Callahan, 1971, Posner, 1973, Bachman and Janiak, 2000 and Ng et al., 2002). Moreover, the processing is operated by a skilled worker. The worker learns how to produce more efficiently during the process. As a result, the jobs deterioration and the learning effect simultaneously exist in the steel rolling mills process. On the other hand, if the temperature of an ingot, while waiting in a buffer between the furnace and the rolling machine, drops below a critical temperature, the ingot needs to be reheated to bring it up to the temperature required for rolling. The reheating time of the ingot depends on its waiting time in the buffer and is thus schedule-dependent, i.e., it requires more time if it is delayed. The reheating process can be considered as a deteriorating maintenance activity. The similar phenomena can also be found in other metal forming processes. Consequently, in this paper we consider single-machine scheduling problems simultaneously with the deterioration and learning effects and deteriorating multi-maintenance activities. We assume that the machine may have multi-maintenance activities during the scheduling horizon. We aim to find jointly the optimal maintenance frequencies, the optimal maintenance locations, and the optimal job schedule to minimize the makespan and the total completion time, respectively. We will provide polynomial time algorithms for all the problems studied. The remaining part of the paper is organized as follows. In Section 2, we formulate the problem. In Sections 3 and 4, we propose polynomial time algorithms for the makespan and the total completion time minimization problems, respectively. Finally, conclusions are given in Section 5.

In this paper we investigated single-machine scheduling problems with simultaneous considerations of the effects of deterioration and learning and deteriorating multi-maintenance activities. We aimed to find the optimal maintenance frequencies, the optimal maintenance locations, and the optimal job schedule to minimize the makespan and the total completion time, respectively. We proposed polynomial time algorithms for both scheduling problems. It is worthwhile for future research to study scheduling problems with other deterioration and learning models, concerning different maintenance duration model, under other shop environments, or involving other performance measures.