Two Due-Date Assignment Scheduling with Location-Dependent Weights and a Deteriorating Maintenance Activity

Traditional scheduling problems consider that the machine is always available, while actually, if a maintenance (rate-modifying) activity is carried out on the machine, it becomes unavailable, and it reverts to its original condition after the maintenance activity is finished (see Lee and Leon [1]; Ma et al. [2]; Strusevich and Rustogi [3]). In 2006, Mosheiov and Oron [4] considered single-machine scheduling with a rate-modifying activity (denoted $rma$). Under the common due-date (denoted $CON$) assignment, the goal is to minimize the total earliness, tardiness and due-date cost. They proved that the problem can be solved in polynomial time. In 2010, Wang and Wang [5] addressed single-machine scheduling with $rma$ and slack due-date (denoted $SLK$) assignment. They showed that the non-regular objective minimization is polynomially solvable. In 2012, Yin et al. [6] studied single-machine batch delivery scheduling with the $rma$ and $CON$ assignment, with the goal of minimizing the sum of earliness, tardiness, due-date, holding and delivery cost. They proved that some special cases of the problem can be solved in polynomial time. In 2014, Bai et al. [7] studied the single-machine problem with deteriorating jobs and $rma$. Under the $SLK$ allocation, the objective is to minimize the weighted sum of earliness, tardiness and the common flow allowance cost. They showed that the problem is polynomially solvable. In 2018, Cheng et al. [8] discussed single-machine batch problems with variable maintenance activities. For the minimization of makespan (total completion time), they demonstrated that the problem can be solved in polynomial time in a special case. In 2019, Detti et al. [9] addressed the single-machine problem with a flexible maintenance activity. In 2021, Wang et al. [10] considered the single-machine problem with $rma$ and a common due-window. For the generalized earliness/tardiness penalties, they showed that the problem is polynomially solvable. In 2022, Zhao et al. [11] studied the single-machine resource allocation problem with an aging effect as well as $rma$ and $SLK$ assignment. In 2023, Sun et al. [12] delved into single-machine scheduling with worsening effects. With the maintenance activity, they showed that some regular objective minimizations are polynomially solvable. For total weighted completion time minimization, they suggested several heuristic and branch-and-bound algorithms. In addition, in 2014, Ji et al. [13] and Fan and Zhao [14] considered due-date assignment scheduling with a deteriorating maintenance activity (denoted $dma$), i.e., the maintenance duration (time) is a linear deteriorating function of the starting time of this maintenance activity. In 2015, Mor and Mosheiov [15] studied single-machine scheduling with $dma$. Under the due-window assignment, they proved that some non-regular minimizations can be solved in polynomial time. In 2017, Li and Chen [16] investigated the single-machine problems with job-rejection and $dma$, and they showed that the makespan, total completion time and due-date assignment minimizations are polynomially solvable. Zhu et al. [17] explored single-machine scheduling with a general (including worsening and resource-dependent) maintenance activity. They showed that the problem can be solved in polynomial time for a number of regular and non-regular objectives. Wang et al. [18] addressed identical parallel machine scheduling with $dma$. They illustrated that the total completion time minimization can be solved in polynomial time. More recent papers which have studied scheduling problems with $rma$ and $dma$ include He et al. [19], Jia et al. [20], liu et al. [21] and Zou et al. [22].

At the same time, in modern manufacturing, more and more industries are adopting due-date assignment systems (see Gordon et al. [23,24], Qian and Zhan [25], Lu et al. [26], Wang [27]) and location-dependent (position-dependent) weights (Brucker [28], Liu et al. [29], Wang et al. [30], Wang et al. [31]). Recently, Jiang et al. [32] investigated proportionate flowshop problems with location-dependent weights. Under the $CON$ and $SLK$ assignments, they showed that the non-regular objective minimization is polynomially solvable (i.e., time is $O(n^{2}logn)$, where n is the number of jobs). Liu et al. [33] studied single-machine scheduling with resource allocation, worsening jobs and location-dependent weights. Under the $CON$ and $SLK$ assignments, they provided a bi-criteria analysis for the scheduling cost (including the weighted sum of the absolute value in lateness and common due date (flow-allowance) cost) and the resource consumption cost. They proved that three versions of these two costs can be solved in polynomial time. In 2021, Lv and Wang [34] considered the same problems as Jiang et al. [32], and they demonstrated that both problems can be addressed by using a lower-order algorithm (i.e., time is $O(nlogn$)). Wang et al. [35] and Wang et al. [36] investigated single-machine scheduling with setup times associated with past sequences and weights related to location. Under the $CON$ and $SLK$ assignments, Wang et al. [35] demonstrated that the weighted sum of earliness, tardiness and due-date cost minimization is polynomially solvable. Wang et al. [36] demonstrated that the weighted sum of lateness, number of early and delayed jobs, and due-date cost minimization is also polynomially solvable.

In real production processes, the location-dependent (position-dependent) weights can be found in services and logistics systems (e.g., in Didi taxi dispatching, Sun et al. [37]). Hence, the work of $CON$ ($SLK$) assignment and $dma$ will be continued by considering the location-dependent weights, i.e., we investigate single-machine due-date assignment scheduling with $dma$ and location-dependent weights. Under the $CON$ and $SLK$ assignments, the aim of the article is to find the job schedule, location of the maintenance activity, and optimal value of common due-date (flow-allowance) so as to minimize the linear weighted sum of the earliness, tardiness and due date assignment costs, where the weights are related to the location. We demonstrate that the problem can be solved in polynomial time, i.e., time complexity is $O\left(n^4\right)$. For a comparison with other similar papers (see Table 1; the related symbols are given later), this article extends the results of Mosheiova and Oron [4], Wang and Wang [5], Brucker [28], and Liu et al. [29], by scrutinizing a more general scheduling model. The rest of this article is structured as below. In Section 2, we introduce the problem. In Section 3 and Section 4, we explore the main details of common due-date and slack due-date assignments. In Section 5, an example and computational experiments are reported to verify the effectiveness of the algorithms. Section 6 presents the conclusion of the problem.

In this article, the problem can be described as: n independent jobs $\{{\check{T}}_1,{\check{T}}_2,\cdots ,{\check{T}}_n\}$ can be usable at time 0 for handling on a single-machine and they are not preemptive. The machine stops working when a maintenance activity is being carried out, if the job ${\check{T}}_i$ is handled before the maintenance activity, the corresponding normal processing time (i.e., basic processing time that is not affected by other factors) is defined as $p_i$, and its actual processing time is $b_i=p_i$. If the job ${\check{T}}_i$ is processed after the maintenance activity, the corresponding actual processing time is defined as $b_i={\epsilon }_i{p}_i$, where ${\epsilon }_i$ is the modified rate of the job ${\check{T}}_i$, and it satisfies $0<{\epsilon }_i\le 1$. Meanwhile, the machine only has a deteriorating maintenance activity, and its maintenance time is: ${\phi }_{\left(t\right)}=t_0+\alpha S_t$, where $t_0$ is the basic maintenance time, $\alpha >0$ is the rate of deterioration, and $S_t$ is the starting time of $dma$. We consider two different types of due-dates that include $CON$ and $SLK$. As for the $CON$ model, all the jobs have the same due date, i.e., $d_i=d_{opt}$, in which $d_{opt}$ is a decision variable. For the $SLK$ model, the due date $d_i$ of job ${\check{T}}_i$ is equivalent to the sum of the actual processing time $b_i$ and the common flow-allowance $q_{opt}$, i.e., $d_i=b_i+q_{opt}$, and the common flow-allowance $q_{opt}$ is a decision variable. For a known schedule $\sigma$, the completion (resp. starting) time of the job ${\check{T}}_i$ is $C_i$ (resp. $S_i$), the earliness (resp. tardiness) cost of the job ${\check{T}}_i$ is $\widetilde{E_i}=max\{0,d_i-C_i\}$ (resp. $\widetilde{L_i}=max\{0,C_i-d_i\}$). Let $\left[i\right]$ be the job being arranged at the ith position in the schedule, then our goal is: (1) to determine the optimal job schedule; (2) to determine where to carry out the maintenance activity of the machine; (3) to determine the value of the common due date and the common flow-allowance; (4) to minimize the objective function: $\dot{Z}={\displaystyle \sum _{i=1}^n}({\mu }_i\widetilde{E_{\left[i\right]}}+{\nu }_i\widetilde{L_{\left[i\right]}}+{\omega }_i{d}_{opt})$ and $\ddot{Z}={\displaystyle \sum _{i=1}^n}({\mu }_i\widetilde{E_{\left[i\right]}}+{\nu }_i\widetilde{L_{\left[i\right]}}+{\omega }_i{q}_{opt})$, where ${\mu }_i$, ${\nu }_i$, ${\omega }_i$ are weights of the ith location in a schedule, i.e., the weights are the location-dependent weights rather than the weights connected with the job ${\check{T}}_i$. With three-field notation, the scheduling can be expressed as:

Assuming that the maintenance activity occurs exactly before the job ${\check{T}}_{\left[i\right]}$, its starting time is equivalent to the completion time of the job ${\check{T}}_{[i-1]}$, i.e., $S_t=C_{[i-1]}$. For the sake of simplicity, let j be the location of the maintenance activity.

From Lemma 1, it can be seen that the jobs before the job ${\check{T}}_{\left[i\right]}$ are the early jobs, and the jobs after the job ${\check{T}}_{\left[i\right]}$ are the late jobs.

Next, we consider the problem $1\left|dma,CON,b_i=(p_i,{\epsilon }_i{p}_i)\right|{\displaystyle \sum _{i=1}^n}({\mu }_i\widetilde{E_{\left[i\right]}}+{\nu }_i\widetilde{L_{\left[i\right]}}+{\omega }_i{d}_{opt})$. Under Lemmas 1–3, the following cases should be considered.

Case 1. If $j\le h$, the schedule is shown in Figure 1.

Where $d_{opt}=C_{\left[h\right]}={\displaystyle \sum _{i=1}^{j-1}}{p}_{\left[i\right]}+\phi \left(t\right)+{\displaystyle \sum _{i=j}^h}{\epsilon }_{\left[i\right]}{p}_{\left[i\right]}$ and $\phi \left(t\right)=t_0+\alpha {\displaystyle \sum _{i=1}^{j-1}}{p}_{\left[i\right]}$. Then the objective function is expressed as where $f_1\left(t_0\right)=t_0\left({\displaystyle \sum _{m=1}^{j-1}}{\mu }_m+{\displaystyle \sum _{m=1}^n}{\omega }_m\right)$ is a constant (if j is given), is only related to the location j of the maintenance activity. Therefore, for a known j, minimizing $\dot{Z}\left(\left[j\right]\right)$ is equivalent to minimizing ${\dot{Z}}_1\left(\left[j\right]\right)$. Let ${\dot{Z}}_1\left(\left[j\right]\right)$ can be minimized by solving the next assignment problem: where ${\beta }_{il}$ is a 0 or 1 variable, if the job ${\check{T}}_i$ is at location l, ${\beta }_{il}=1$, otherwise ${\beta }_{il}=0$.

Case 2. If $j>h$, the schedule is shown Figure 2.

Where ${d_{opt}=C}_{\left[h\right]}={\displaystyle \sum _{i=1}^h}{p}_{\left[i\right]}$, and $\phi \left(t\right)=t_0+\alpha {\displaystyle \sum _{i=1}^{j-1}}{p}_{\left[i\right]}$. Then the objective function is expressed as where $f_2\left(t_0\right)=t_0{\displaystyle \sum _{m=j}^n}{\upsilon }_m$ is only related to $t_0$ and it is a constant, is only related to the location j of the maintenance activity. Similarly to Case 1 (i.e., $j\le h$), let then, the problem can be translated into the assignment problem below: where ${\gamma }_{il}$ is a 0 or 1 variable, when the job ${\check{T}}_i$ is at position l, ${\gamma }_{il}=1$, otherwise ${\gamma }_{il}=0$.

Case 3. If $j=n+1$, the schedule is shown Figure 3.

where ${d_{opt}=C}_{\left[h\right]}={\displaystyle \sum _{i=1}^h}{p}_{\left[i\right]}$ and $\phi \left(t\right)=t_0+\alpha {\displaystyle \sum _{i=1}^n}{p}_{\left[i\right]}$. This means that there is no maintenance activity on the machine. In this case, the objective function is where

The optimal schedule $\sigma$ as well as the minimum value of $\dot{Z}$ can be acquired by matching the minimum weight ${\pi }_i$ with the maximum processing time $p_i$ by using $HLP$ rule (see Lemma 3).

Case 4. if $j=1$, the schedule is shown Figure 4.

where ${d_{opt}=C}_{\left[h\right]}={\displaystyle \sum _{i=1}^h}{\epsilon }_{\left[i\right]}{p}_{\left[i\right]}+\phi \left(t\right)$, and $\phi \left(t\right)=t_0$. This means that the maintenance activity occurs before the jobs are processed. In this case, the objective function is where $f_3\left(t_0\right)=t_0{\displaystyle \sum _{m=1}^n}{\omega }_m$ is only related to $t_0$ and it is a constant. Similarly, the optimal schedule of this case can be obtained through Lemma 3.

From the above cases, the optimal solution of the problem $1\left|dma,CON,b_i=(p_i,{\epsilon }_i{p}_i)\right|{\displaystyle \sum _{i=1}^n}$ $({\mu }_i\widetilde{E_{\left[i\right]}}+{\nu }_i\widetilde{L_{\left[i\right]}}+{\omega }_i{d}_{opt})$ can be obtained by using the following algorithm.

Next, we investigate the problem $1\left|dma,SLK,b_i=(p_i,{\epsilon }_i{p}_i)\right|{\displaystyle \sum _{i=1}^n}({\mu }_i\widetilde{E_{\left[i\right]}}+{\nu }_i\widetilde{L_{\left[i\right]}}+{\omega }_i{q}_{opt})$. Under Lemmas 3–5, the following cases will be considered.

Case 5. If $j\le h$, the schedule is identical to Case 1, where $q_{opt}=S_{\left[h\right]}={\displaystyle \sum _{i=1}^{j-1}}{p}_{\left[i\right]}+\phi \left(t\right)+{\displaystyle \sum _{i=j}^{h-1}}{\epsilon }_{\left[i\right]}{p}_{\left[i\right]}$ and $\phi \left(t\right)=t_0+\alpha {\displaystyle \sum _{i=1}^{j-1}}{p}_{\left[i\right]}$. Then the objective function is expressed as where $f_1\left(t_0\right)$ is the same as it in Case 1, and is only related to the position of j. Therefore, for a known j, minimizing $\ddot{Z}\left(\left[j\right]\right)$ is identical to minimizing ${\ddot{Z}}_3\left(\left[j\right]\right)$, and ${\ddot{Z}}_3\left(\left[j\right]\right)$ can be minimized by resolving the assignment problem. Let ${\rho }_{il}$ represent the weight of job ${\check{T}}_i$ at location l, i.e.,

The problem can be translated into the assignment problem below: where ${\chi }_{il}$ is a 0 or 1 variable, if the job ${\check{T}}_i$ is at position l, ${\chi }_{il}=1$, otherwise ${\chi }_{il}=0$.

Case 6. If $j>h$, the schedule is the same as Case 2, where ${q_{opt}=S}_{\left[h\right]}={\displaystyle \sum _{i=1}^{h-1}}{p}_{\left[i\right]}$, and $\phi \left(t\right)=t_0+\alpha {\displaystyle \sum _{i=1}^{j-1}}{p}_{\left[i\right]}$. Then the objective function is stated as where $f_2\left(t_0\right)$ same as it in Case 2, and is only related to the location of the maintenance activity. Similarly to Case 5 (i.e., $j\le h$), let