به حداقل رساندن فاصله زمانی تولید در برنامه ریزی یک ماشین با اثر فرسودگی و فعالیت های تعمیر و نگهداری متغیر

This paper considers a single-machine scheduling with a position-dependent aging effect described by a power function under maintenance activities and variable maintenance duration considerations simultaneously. We examine two models of the maintenance duration in this study. The objective is to find jointly the optimal maintenance frequency, the optimal maintenance positions, and the optimal job sequences to minimize the makespan of all jobs. We provided polynomial time solution algorithms for all the studied problems.

Traditionally, the processing time of jobs is assumed to be independent of its position or starting time in a scheduling sequence. However, there are many situations in which the actual processing time of jobs may be subject to change due to the effect of learning, aging, or deterioration. In scheduling with the learning effect, the actual processing time of a job is modeled as a decreasing function if it is scheduled later in a sequence, while in scheduling with the aging effect the actual processing time of a job is modeled as an increasing function if it is scheduled later in a sequence. On the other hand, in scheduling with the effect of deterioration, the actual processing time of a job is an increasing function of its starting time. Scheduling problems with the learning effect, the aging effect, or the deteriorating effect have received increasing attention in recent years. For details on this stream of research, time-dependent scheduling problems are discussed in surveys [1] and [2] and book [3], while position-dependent scheduling problems are discussed in reviews [4], [5] and [6]. Recently, some researchers proposed new models or new approaches to machine scheduling with issues of the learning effect or the aging effect. Inderfurth et al. [7] explored a production system with batching work and rework processes. They assumed that there is a given deterioration time limit for the reworked item. Janiak and Rudek [8] extended a classical position-dependent model to an experience-based learning model to minimize the makespan. Janiak and Rudek [9] investigated a scheduling problem with a new learning effect model, where the learning curve is described by experience dependent stepwise functions that are not restricted to a certain learning curve. Later, Janiak and Rudek [6] provided an extensive study of a single-machine scheduling with an experience-based learning model, where job processing times are described by S-shaped functions that are dependent on the experience of the machine. They showed that the makespan minimization problem is NP-hard or strongly NP-hard with most of the considered learning models. Lin [10] studied a scheduling problem with a general job-dependent learning model on a single-machine. He showed that the number of late jobs minimization problem is strongly NP-hard when due-dates of jobs are different. Janiak and Rudek [11] further improved the proof of the study of Lin [10]. Janiak and Rudek [12] generalized the existing models of the aging effect to minimize the makespan on a single-machine with release dates. Janiak and Rudek [13] introduced the concept of multi-ability learning that generalizes the existing ones and models more precisely in real-life settings. Moreover, there are also some special models or approaches to scheduling problems with the learning effect or the aging effect. The reader can refer to Janiak et al. [14], Yin et al. [15], Cheng et al. [16], Yang et al. [17], and Lee et al. [18]. In real production systems, maintenance is important to production as it helps improve the production efficiency or the product quality. During the maintenance, machine is not available for processing jobs. Scheduling in such an environment is specified as scheduling with availability constraints and it has attracted many researchers. Sanlaville and Schmidt [19], Schmidt [20], and Ma et al. [21] provided extensively surveys related to machine scheduling problems with the maintenance. Furthermore, the studies of scheduling with simultaneous considerations of the job deterioration and the maintenance have been popular topics to researchers. Wu and Lee [22] explored a single-machine scheduling with deteriorating jobs under a resumable availability constraint. The aim was to find an optimal schedule to minimize the makespan. Ji et al. [23] investigated the problem similar to Wu and Lee [22] under the non-resumable situation. The objectives were to minimize the makespan and the total completion time. Gawiejnowicz [24] studied two problems of scheduling a set of independent, non-preemptive and proportionally deteriorating jobs on a single-machine with constraints on availability of the machine or jobs and the maximum completion time criterion. Low et al. [25] considered a single-machine scheduling with an availability constraint to minimize the makespan under a simple linear deterioration. Lodree and Geiger [26] explored a single-machine scheduling with time-dependent processing times and a rate-modifying activity. The goal was to derive the optimal policy for assigning a single rate-modifying activity in a sequence to minimize the makespan. Gawiejnowicz and Kononov [27] studied a single-machine scheduling with simultaneous considerations of time-dependent deteriorating jobs and a machine available constraint in a resumable situation to minimize the maximum completion time of all jobs. In the past, however, most research on scheduling with the maintenance assumed that at most one maintenance is allowed to a machine throughout the scheduling horizon. Nevertheless, in real production settings, the machine may need to maintain more than once to improve the production efficiency or the product quality. Therefore, a more realistic machine scheduling model should take multiple maintenance activities into consideration. Chen [28] explored a single-machine scheduling problem of minimizing total tardiness while taking multiple tool changes into account. Two mixed binary integer programming models were developed to optimally solve the problem. Chen [29] considered a single-machine scheduling to minimize the number of tardy jobs subject to periodic maintenance activities and non-resumable jobs. He developed an effective heuristic based on Moore's algorithm to produce near-optimal solutions, and presented a branch-and-bound algorithm to find the optimal solution. Kuo and Yang [30] studied a single-machine scheduling with a cyclic process of the aging effect and maintenance activities. They investigated the makespan problem with position-dependent aging effect models and provided polynomial time algorithms to solve them. Zhao and Tang [31] extended the study of Kuo and Yang [30] to the case with the position-dependent aging effect described by a power function. They provided a polynomial time algorithm for the problem. In addition, most research considered scheduling with the maintenance assumed that the maintenance duration is a constant no matter what the condition of the machine or operator is. However, this assumption may be invalid in many practical situations due to the uncertainty of the machine or the operator condition. The maintenance duration may depend on the running time of the machine, in that the later maintenance is performed; the worse the machine conditions are, a longer time is needed to perform the maintenance. By contrast, the maintenance duration may decrease by repeating the same operating processes due to the learning effect of the operator. This kind of maintenance activity can be considered as a variable maintenance activity. Several recent papers have been conducted to address the variable maintenance activity on scheduling problems [17], [32], [33] and [34]. To the best of our knowledge, scheduling with the aging effect under maintenance activities and variable maintenance duration considerations simultaneously has rarely been explored. Motivated by observations in practical manufacturing, e.g., the metal forming process, this study investigates a single-machine scheduling with simultaneous considerations of the aging effect and variable maintenance activities. We assume that the machine may be subject to several maintenance activities during the scheduling horizon and the duration of each maintenance is a variable function. The objective is to find jointly the optimal maintenance frequency, the optimal maintenance positions, and the optimal job sequences to minimize the makespan of all jobs. We will show that all the studied problems are polynomially solvable. The remainder of this paper is organized as follows. In the next section we formulate the problem. In Section 3 we provide polynomial time solution algorithms for variants of the problem. We conclude the findings in the last section.

In this paper, we investigated a single-machine scheduling with a position-dependent aging effect described by a power function under maintenance activities and variable maintenance duration considerations simultaneously. We showed that all the studied problems can be optimally solved in polynomial time. Table 1 lists the time complexity results for various cases of the problem. Results of this study can be extended to the problem with other models of the aging effect, e.g., a linear position-dependent aging effect model (pjr=pj+bjrpjr=pj+bjr). Further research may investigate other models of maintenance duration and multi-machine settings, or other performance measures.