# Stochastic Dynamic Programming
for Earliness-Tardiness Single Machine Scheduling with
Maintenance Considerations

Sabri Abderrazzak, Allaoui Hamid, Souissi Omar

► To cite this version:

Sabri Abderrazzak, Allaoui Hamid, Souissi Omar. Stochastic Dynamic Programming for Earliness-Tardiness Single Machine Scheduling with Maintenance Considerations. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.269-276, 10.1007/978-3-030-85914-5_29. hal-03897848

HAL Id: hal-03897848

https://inria.hal.science/hal-03897848

Submitted on 14 Dec 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
Stochastic dynamic programming for
earliness-tardiness single machine scheduling
with maintenance considerations

SABRI Abderrazzak$^{1,2}$, ALLAOUI Hamid$^{1}$, and SOUISSI Omar$^{2}$

¹ Univ. Artois, EA 3926, Laboratoire de Génie Informatique et d'Automatique de l'Artois (LGI2A) Béthune, France

² Institut national des postes et télécommunications, Rabat, Morocco

**Abstract.** We study in this paper the problem of simultaneously schedul-
ing resumable jobs and preventive maintenance on a single machine to
minimize the earliness-tardiness cost. The machine is subject to random
breakdowns according to Erlang distribution and minimal repair is con-
sidered. The age of the machine defines its probability of breakdown
and performing preventive maintenance renews the age of the machine
to zero, however the preventive maintenance operations cost valuable
time that can increase the overall earliness-tardiness cost. A stochas-
tic dynamic programming solving approach is presented for solving this
problem with illustrated meaning to its algorithm.

**Keywords:** Preventive maintenance · Dynamic programming · Production scheduling.

# 1 Introduction

In all industrial contexts, production is the main function of the system and the
essential source of value, and should ideally be continuously active, and as every
order have to be delivered on a prefixed due date, the optimal sequence in which
orders should be fed to the machine is often not obvious, the earliness-tardiness
model is one of many used to optimize this process, it aims at finishing orders
following a just-in-time performance strategy, as quick response to customer's
orders and respecting their delivery dates is key to success in the manufacturing
business, however finishing jobs too early increases the stocking and warehous-
ing costs and further lowers the profit margin, this strategy has been adopted
by many big companies (Apple, McDonald's, Toyota ..) and was proven to be
successful at lowering the cost of goods while keeping the customers satisfied.

However, production systems are not ideal and tend to fail regularly due to
over usage or equipment failure, so while it is already not evident to schedule
production jobs, the randomness of failure events adds another layer of difficulty
to the task of production scheduling. To assert a certain level of control over the
random aspect of breakdowns, preventive maintenance PM is performed, and
while it does not exclude the possibility of failure, it fairly reduces the increasing
risk of machine breakdown. However, performing preventive maintenance costs valuable time that could be used for production, while not performing it presents the machine to the increasing risk of failure, hence the trade-off.

The literature around this problem is extensive, especially in the areas of operational research and production systems, however, the majority of these papers considers that the machines are available at all times, and no maintenance is needed, and since this is often not true as we explained industrial machines tend to fail regularly, we in this paper treat the case of scheduling N jobs on a single machine considering the possibility of machine failure.

## 2 STATE OF THE ART

Among the first attempts to solve the problem of single machine scheduling with common due date and earliness-tardiness penalties, [1] studied the general case where the due date is not prefixed and is to determine. The method proposed by authors consists of assigning the optimal due date as well as the optimal feasible sequence of jobs that minimize the sum of earliness tardiness penalties and cost of due date assignment, more in depth, for a set of N jobs all available at time zero, and $C_j$ being the completion time of a job j, the goal is to determine a due date $D^*$ and a feasible sequence $\sigma^*$, that minimize the objective function

$$f(d, \sigma) = \sum_{j=1}^{n} \alpha E_j + \beta T_j$$

with $E_j = \max(d - C_j, 0)$ and $T_j = \max(C_j - d, 0)$ denoting respectively the earliness and tardiness of job j, and $\alpha, \beta$ being the respective cost coefficients of earliness and tardiness.

A huge interest in the scheduling with due date assignment sparked after the work of [1], different generalizations of the problem were proposed, such as replacing the common due date with common due window [1], the consideration of due date tolerance [4], ... etc. For a more detailed review of these works, we refer the readers to the survey of [2].

On a less generalized level, we are most interested in the case where the common due date is predetermined. In such a problem, the objective is to determine the optimal feasible sequence $\sigma^*$ for which the simplified function

$$f(d, \sigma) = \sum_{j=1}^{n} \alpha E_j + \beta T_j$$

is minimized. [5] proposed an enumerating algorithm to solve the variant of the problem where ($\alpha = \beta = 1$), later to that [6] proposed dynamic programming algorithm that solves the problem in pseudo polynomial time,[7] also proposed a DP algorithm with pseudo-polynomial run time as well as a branch-and-bound method based on a Lagrangian lower-and-upper bounds. For the variants where $\alpha_j$ and $\beta_j$ are constants ($\alpha_j = \alpha, \beta_j = \beta$), [8] proposed a branching procedure, however his method only work for small sized instances. The case of ($\alpha_j \neq \beta_j$)
was only solved with the help of approximation methods, like the work of [9] where a meta-heuristic was used to obtain approximate solutions.

All works above assume that the machine is available at all times, however, the problem of job scheduling where the machine is subject to failure and breakdowns is very lightly studied in the literature. [10] was among the earliest and few efforts aimed in this direction as authors studied the case where the machine is subject to external shocks following a non-homogeneous Poisson process, [11] considers stochastic model for breakdowns. A more elaborated effort was made by [12] where they considered that breakdowns follow an Erlang distribution and presented a stochastic dynamic programming algorithm for preventive maintenance scheduling that minimizes earliness-tardiness costs. [14] presented a model that solves the job scheduling based on periodic preventive maintenance performance, and in a very similar fashion, [13] also uses a periodic maintenance scheduling to solve the problem. [18] also defines a periodic planning for preventive maintenance where the interval for PM is dynamically updated while scheduling the jobs. [16] proposed a mixed-integer linear programming model to simultaneously schedule the production and maintenance tasks, optimizing the earliness-tardiness costs as well as a wide range of objectives (preventive maintenance costs, idle-time costs, components and assembly costs ..). [17] successfully integrated production and preventive maintenance in a single mathematical model to simultaneously schedule both activities while optimizing the due-date meeting and machine availability. Following the recent trends in the scientific literature, [19] and [20] used the deep Q-Learning algorithm to learn an optimal policy to jointly schedule production jobs and maintenance operations.

## 3 PROBLEM STATEMENT

The problem of job scheduling with preventive maintenance has been solved using dynamic programming for non-resumable jobs, we in this paper consider the resumable case, where in the event of breakdown, the progress made so far on the job is not lost, and the machine can resume working on it after repair from the last progress point.

This paper divides problem to two steps, first we assume that the machine is available at all times, and solve the job scheduling with common due date using a dynamic programming algorithm, where for an input of N jobs and their respective processing time, we expect as output a sequence of the jobs for which the earliness tardiness cost is minimal, then we further elaborate the solution considering the element of preventive maintenance and breakdowns, using a stochastic dynamic programming model, that take as input the solution of the first step, and prior to the execution of each job, we decide optimally whether to perform preventive maintenance or not.

let $C_{ET}$ be the cost function for a sequence of jobs $S$ and a due date $D$:

$$C_{ET}(S, D) = \sum_{j \in S} (\alpha_j E_j + \beta_j T_j)$$
## 3.1 DETERMINISTIC DYNAMIC PROGRAM

Here, we are concerned with the total ‘weighted earliness-tardiness (WET)” in which the jobs have different weights $w_j$ but a common due date that is loose; $\alpha_j=\beta_j=w_j$ and $d_j = d$. The approach is solved to optimality via DP and is based on the work of [15]. The procedure is pseudo-polynomial.

As before, call the set of early jobs E and the set of tardy job T. The efficiency of the algorithm depends crucially on the third Property mentioned in [15], namely, the fact that all jobs in either subset E or T must be ordered in decreasing ‘weighted shortest processing time (WSPT)” order measured (in absolute value) from time D as the origin. The proof of this assertion is evident when one considers each subset by itself with time measured away from D.

Based on this property one starts by re-arranging the jobs in WSPT. This constitutes the list of the jobs from which selection shall be made. If job k is selected for placement on the machine it must be true that all preceding jobs 1 through $k-1$ must have been placed on the m/c either in E or in T. This leads to the definition of the “stages” as progressing from 1 to n; stage k involves the first k jobs in the list. Let $W_k \subseteq N$ denote the set of the first k jobs in the list, where N denotes the set of all jobs $W_k = 1, ..., k$.

At stage k the total occupancy of the machine must be $P(W_k) = \sum_{i=1}^{k} p_i$, observe that the total processing time of any subset of jobs is constant independent of their sequence, and independent of whether or not they straddle d, though we know that in an optimal sequence, no job will straddle d, but some job in E must end at d and some job in T must start at d, assuming that no $\alpha_j$ or $\beta_j$ is equal to 0.

Let e denote the sum of the processing times of the subset of jobs in $W_k$ that are early (in set E, to the left of D). Alternatively, we could have selected t as the sum of the processing times of the subset of jobs in $W_k$ that are Tardy (in set T, to the right of D); but we shall stick with e. Then the tardy jobs (in set T, to the right of D) complete at time $P_k - e$;

Shift the origin to d and measure all times from d in either direction. Job k is either in E or in T. If it is in E then it is placed first (farthest from d) and its completion time shall be $(e - p_k)$; and its cost is $w_k$ $(e - p_k)$. If it is placed in T then it is placed last (again, farthest from D) and its completion time shall be $(P(W_k) - e)$; and its cost is $w_k$ $(P_k - e)$.

Let $f_k(e)$ denote the minimal cost to schedule the set $S_k$ composed of jobs 1 through k when the jobs in $E \subseteq S_k$ occupy time e. Then we are led to the extremal equation,

$$f_k(e) = \min \begin{cases} a_k(e - p_k) + f_{k-1}(e - p_k), & \text{if job } k \text{ is placed} \\ b_k \cdot (P(W_k) - e) + f_{k-1}(e), & \text{if job } k \text{ is placed} \\ 0 & \text{in } E, e \ge p_k \\ 0 & \text{in } T, P_k - e \ge p_k \end{cases}$$

which is initiated at $f(.) = 0$
and terminated when $f_n(e)$ is evaluated for all feasible e and the minimum is determined. Observe that in the determination of $f_k(e)$ either of the two options may be infeasible, in which case the corresponding value f would be put $\infty$ to prohibit its adoption

THE ALGORITHM

Initiate the DP iterations with: $f_0(e) = 0$, for $e = 0, 1, 2, ..., \sum_{j=1}^{n} p_j$

and terminate it when the minimum cost schedule is found at $f_n(0)$. By the WSPT order there is one set $S_k = 1, ..., k$. At stage k one enumerates over the values of e, which ranges from 0 to $P(W_k)$ Therefore the complexity of the DP procedure is seen to be $O(n \sum_{j=1}^{n} p_j)$; it is pseudo-polynomial.

3.2 STOCHASTIC DYNAMIC PROGRAM

After solving the first part, we now consider the possibility of machine break-down, we consider that breakdown events occur following the Erlang distribution for which the density function is defined as :

$$f(x; k, \lambda) = \frac{\lambda^k x^{k-1} e^{-\lambda x}}{(k-1)!} \quad \text{for } x, \lambda \ge 0,$$

For a given job in the optimal sequence given by part 1 starting at time t, and for which the processing time is $p_j$, we define the probability of a breakdown event happening during its execution by: $P(t) = \int_0^t f(x)dx$. We also define $a_j$, the age of the machine before executing the job j,

Now before executing job j, we have to choose between two decisions:

<figure><img src="image_3.png" /><figcaption>Fig. 1. PM IS PERFORMED (1); PM IS NOT PERFORMED AND : NO BREAK-DOWNS OCCUR (2), A BREAKDOWN OCCURS (3)</figcaption></figure>

1. Perform preventive maintenance, which takes $T_{PM}$ amount of time, and reduces the probability of breakdown to zero as we maintain the machine to as-new condition, it also resets the age of the machine to zero,

2. Do not perform preventive maintenance and proceeds directly to the treating of job j, this leads to two possible outcomes:
- The machine does not breakdown, which happens with probability 1 - $p(a_j)$, the job j is finished at time $t+p_j$, and the age of the machine at the end of job j is $a_j+p_j$

- A breakdown event occurs, which happens with probability $p(a_j)$, a repair operation of duration $T_R$ is necessary, the progress made before the breakdown is not lost and the machine will resume the job after repair from the last progress point. The job finishes at time $t + T_R + p_j$. The repair is minimal, which means the machine is repaired just enough to start operating again, and it does not affect its age. The age at end of execution is $a_j+p_j$.

## THE FORMULATION

To solve this problem, we formulate a dynamic programming algorithm for instances where $(\alpha_j=\beta_j=1)$, $(\alpha_j = \beta_j)$ and $(\alpha_j = \alpha, \beta_j = \beta)$.

First, we order the optimal sequence from part 1 in reverse from n to 1, and then for every stage of the DP, we evaluate the cost of both decisions.

For the case of $d_j = 1$, it is simple to see that the cost of stage j is $C_{ET}(t + T_{PM} + p_j)$, however for the case of $d_j = 0$ where the machine has two possible scenarios, the total cost at time t is either $C_{ET}(t + p_j)$ in case no breakdown happened, or $C_{ET}(t + p_j + T_R)$ in the scenario where a breakdown occurs, both outcomes happen with respective probabilities $1-p(a_j)$ and $p(a_j)$, so to estimate the expected cost of the decision $d_j = 0$, we calculate the weighted cost of both cases.

The state of the dynamic programming model at any stage is given by the time and the age of the machine, and let $f_n(t, a)$ be the expected cost of stages $j, j + 1, \dots, n$ when considered at time t with age a. As we start the iterations on the stages backwards, the base case for our model stands at $j = n$, for that we give :

$$f_n(t, a) = \min_{d_j=0,1} \{C_{ET} \times p(a_j) + C_{ET} \times \overline{p(a_j)}\}$$

After stage n, for any $1 \le j < n$, the cost of stage j when considered at time t with age a is given by the recursive formula :

$$f_j(t, a_j) = \min_{d_j=0,1} \left\{ C_{ET}(t_1) \times p(a_j) + C_{ET}(t_2) \times \overline{p(a_j)} + f_{j+1}(t_1, a_{j+1}) \cdot p(a_j) + f_{j+1}(t_2, a_{j+1}) \cdot p(a_j) \right\}$$

with :

$$- \overline{p(a_j)} = 1 - p(a_j)$$

$$- t_1 = t + T_R + p_j$$

$$- t_2 = t + T_{PM} \times d_j + p_j$$

$$- a_{j+1} = a_j \times (1 - d_j) + p_j$$

It is obvious that in an optimal solution, the start time of the first job is less than D, and considering that the age of the machine is zero ($a_1 = 0$) at the start of the sequence, we calculate the variable intervals for each stage knowing that the start time of the sequence is in the $(0, D)$ interval
$$T_{\max} = D + \sum_{j=1}^{n} p_j + \max(T_{\text{PM}}, T_{\text{R}}), \quad a_{\max} = \sum_{j=1}^{n} p_j : \text{For stage 1.}$$

$$T_{\max} = T_{\max} - p_{j-1} - \max(T_{\text{PM}}, T_{\text{R}}), \quad a_{\max} = a_{\max} - p_{j-1} : \text{For stage } j \in [2, n]$$

The problem is solved when we reach $j = 1$, we can get the optimal sequence of preventive maintenance decisions as well as the start time of the first job in the sequence by finding the minimal value of cost in stage n, then climb back up the table to stage 1 to formulate the decision tree.

## 4 CONCLUSION

In this paper we have studied the problem of job scheduling with preventive maintenance on a single machine using stochastic dynamic programming to minimize the earliness tardiness cost relative to a common due date, this problem is particularly understudied in the industrial production research community, whereas production units with scheduling systems that do not factor maintenance and breakdowns in the planning procedure suffer from uncertainty in delivery dates, and are hugely under-performing. The two-steps algorithm that we propose to solve the problem consist of initially solving the problem of scheduling n jobs with no breakdowns considered, the solution obtained from this step is then used as an input to the second phase where we consider breakdowns following the Erlang distribution and solve the problem of preventive maintenance planning for the sequence obtained in the first step. The final output is a decision tree that defines the optimal decisions based on how the stochastic event of breakdowns play out in time. In future works, since the method we present schedules the jobs and maintenance tasks on a single machine only, we are most interested in generalizing the existing model to a job-shop use case. In addition, dynamic programming is computationally expensive and is only efficient for small numbers of jobs, therefore we also consider exploring the use of recent advances in artificial intelligence to solve this problem with lower computational cost.

## 5 ACKNOWLEDGMENT

This work is a part of the ELSAT2020 project. The ELSAT2020 project is cofinanced by the European Union with the European Regional Development Fund, the French state and the Hauts de France Region Council.

## References

1. A Seidmann, SS Panwalkar, ML Smith "Optimal assignment of due-dates for a single processor scheduling problem"- The International Journal Of Production Research, 1981

2. Gordon, Valery, Jean-Marie Proth, and Chengbin Chu. "A survey of the state-of-the-art of common due date assignment and scheduling research." European Journal of Operational Research 139.1 (2002): 1-25.
3. Liman, S. D., S. S. Panwalkar, and S. Thongmee. "Common due window size and location determination in a single machine scheduling problem." Journal of the Operational Research Society 49.9 (1998): 1007-1010.

4. Cheng, T. C. E., and M. C. Gupta. "Survey of scheduling research involving due date determination decisions." European journal of operational research 38.2 (1989): 156-166.

5. Bagchi, Uttarayan, Robert S. Sullivan, and Yih-Long Chang. "Minimizing mean absolute deviation of completion times about a common due date." Naval Research Logistics Quarterly 33.2 (1986): 227-240.

6. Hall, Nicholas G., and Marc E. Posner. "Earliness-tardiness scheduling problems, I: weighted deviation of completion times about a common due date." Operations Research 39.5 (1991): 836-846.

7. Hoogeveen, Johannes Adzer, and Steef L. van de Velde. "Earliness-tardiness scheduling around almost equal due dates." INFORMS Journal on Computing 9.1 (1997): 92-99.

8. Bagchi, Uttarayan, Robert S. Sullivan, and Yih-Long Chang. "Minimizing mean squared deviation of completion times about a common due date." Management Science 33.7 (1987): 894-906.

9. James, Ross JW. "Using tabu search to solve the common due date early/tardy machine scheduling problem." Computers & Operations Research 24.3 (1997): 199-208.

10. Pinedo, Michael L., and Sheldon M. Ross. "Scheduling jobs subject to nonhomogeneous Poisson shocks." Management Science 26.12 (1980): 1250-1257.

11. Birge, John, et al. "Single-machine scheduling subject to stochastic breakdowns." Naval Research Logistics (NRL) 37.5 (1990): 661-677.

12. Allaoui, Hamid, et al. "Scheduling n jobs and preventive maintenance in a single machine subject to breakdowns to minimize the expected total earliness and tardiness costs." IFAC Proceedings Volumes 41.2 (2008): 15843-15848.

13. Benmansour, Rachid, et al. "Minimizing the weighted sum of maximum earliness and maximum tardiness costs on a single machine with periodic preventive maintenance." Computers & Operations Research 47 (2014): 106-113.

14. Todosijievic, Raca, et al. "Optimizing the periodic maintenance problem using General Variable neighbourhood search." ROADEF-15ème congrès annuel de la Société française de recherche opérationnelle et d'aide à la décision. 2014.

15. Alidaee, Bahram. "Schedule of n jobs on two identical machines to minimize weighted mean flow time." Computers & industrial engineering 24.1 (1993): 53-55.

16. Chansombat, S., Pongcharoen, P., Hicks, C. (2019). A mixed-integer linear programming model for integrated production and preventive maintenance scheduling in the capital goods industry. International Journal of Production Research, 57(1), 61-82.

17. Kolus, A., El-Khalifa, A., Al-Turki, U. M., Duffuaa, S. O. (2020). An integrated mathematical model for production scheduling and preventive maintenance planning. International Journal of Quality Reliability Management.

18. Ye, H., Wang, X., Liu, K. (2020). Adaptive Preventive Maintenance for Flow Shop Scheduling With Resumable Processing. IEEE Transactions on Automation Science and Engineering, 18(1), 106-113.

19. Yang, H., Li, W., Wang, B. (2021). Joint optimization of preventive maintenance and production scheduling for multi-state production systems based on reinforcement learning. Reliability Engineering System Safety, 214, 107713.
20. Huang, J., Chang, Q., Arinez, J. (2020). Deep reinforcement learning based pre-ventive maintenance policy for serial production lines. Expert Systems with Ap-plications, 160, 113701.