A parallel-machine scheduling with periodic constraints under uncertainty

Abstract

Most studies on scheduling problem have assumed that the machine is continuously available. However, the machine is likely to be unavailable for many practical reasons (e.g. breakdown and planned preventive maintenance). Once a machine is not available, the optimal scheme in the deterministic scenario may not be the optimal choice. To address the actual scenario, a scheduling problem with two identical parallel machines, one of which requires periodic maintenance, is considered in this article. For uncertainties in reality, the processing and maintenance time are considered as uncertain variables. A novel method to study the worst-case ratio in an uncertain scenario is proposed. It is shown that the worst-case ratio of the longest processing time algorithm is 3/2 at a high confidence level. Given theoretical analysis results, an modified algorithm is proposed. Finally, numerical experiments are used to verify the feasibility of the modified algorithm.

Introduction

In recent years, scheduling problems with machine availability constraints have aroused increasing attentions. In practice, machine breakdown may often happen during the process operation. If a machine breaks down accidentally, the quality of outputs is likely to be affected. To expand life expectancy of a machine, regular preventive maintenance activities are essential. The machine should stop when undergoing maintenance. The parallel-machine scheduling refers to a typical NP-hard optimization problem. This type of minimization problems concern the performance of any efficient heuristic algorithm over the worst-case choice of inputs. The worst case ensures that approximation algorithms are applicable even in the contexts where there is little or no additional information available about the inputs. The worst-case ratio can be adopted to compare the quality of the algorithm, so it is vital.

Numerous results regarding scheduling problems with interval constraint have been achieved. Note that most of the studies on the interval constraint focuses on the development of algorithms or the worst case bound. Lee ¹ considered single-machine and parallel-machine scheduling problems with preventive maintenance, and the worst-case ratios of algorithms under different performance measures were calculated. According to Liao and Chen, ² a single-machine scheduling problem with interval constraints was investigated, and an efficient branch-and-bound algorithm was proposed. Wang and Cheng ³ analyzed a two-identical-parallel-machine scheduling under the interval constraint to maximize the number of on-time jobs. Liu et al. ⁴ explored two online scheduling problems with interval constraints. The first one is $m$ parallel-machine online scheduling where one machine with periodic unavailability constraints, and the other is two-uniform-parallel-machine online scheduling, and two corresponding algorithms were given. According to Koulamas and Kyparisis, ⁵ a delayed-start longest processing time (LPT) algorithm was proposed for an identical parallel-machine scheduling problem. Results suggested that this algorithm exhibits a sharper tight worst-case ratio bound than the LPT algorithm. Koulamas and Panwalkar ⁶ considered a two-machine no-wait job shop scheduling problem. Results revealed that the complexity of the problem is dependent on the presence of missing operations and the allocation of the missing operations to the machines. Oron et al. ⁷ analyzed a workload partition problem (WPP) on $m$ identical parallel machine. They presented two approximation algorithms for the problem. Xu et al. ⁸ studied a two-parallel-machine scheduling problem with periodic constraint. Besides, LPT and list scheduling (LS) algorithms were adopted to calculate the worst-case ratios. According to Li et al., ⁹ two mathematical programming models were developed for parallel-machine scheduling with periodic maintenance, and two improved heuristic algorithms based on worst-case analysis of LPT and LS were proposed. Pacheco et al. ¹⁰ developed an improved single-machine scheduling model with periodic maintenance. To solve large-sized instances, they proposed an efficient heuristic method based on the Variable Neighborhood Search (VNS). Wang et al. ¹¹ developed a single-machine scheduling model with flexible periodic maintenance and proposed a branch-and-price (BP) algorithm for the problem. Nesello et al. ¹² presented mathematical models for the single-machine scheduling problem with periodic maintenances and sequence-dependent setup times and developed an iterative exact algorithm. According to the results of extensive computational experiments, the proposed algorithm outperforms the existing one. Perez-Gonzalez and Framinan ¹³ presented a mixed integer linear programming model for single-machine scheduling with periodic maintenance. They also developed a heuristic algorithm from bin-packing problem.

Some mentioned literature assumed that there is only one unavailability constraint. However, it is generally impossible that machine failure or preventive maintenance will occur only once. Thus, it is quite meaningful to consider more than one unavailability constraint. Periodic maintenance includes periodic inspections, periodic repairs, and preventive maintenance. If maintenance plans can be arranged in an orderly manner, production efficiency of the enterprise can be improved, and the safety consciousness of workers can be strengthened. Indeed, some of the previously mentioned literature also considered periodic maintenance. But when they discuss this issue, their methods should often be split into many situations. Accordingly, when the number of machines increases, the proposed method is generally inefficient. This article proposes a method that can effectively solve the problem and effectively shorten the certification process.

Almost all existing literature considered this type of problems in a deterministic or random environment. Given the complexity of the real environment, numerous man-made factors exert a potential influence on scheduling horizon. These influences may be uncertain events that cannot be modeled with probability distributions. Experts should be invited to assess the belief degree that an uncertain event will occur. To address belief degrees, Liu ¹⁴ established the uncertainty theory. The uncertainty theory is a branch of axiomatic mathematics for modeling human uncertainty, which have many research results of uncertain programming.^15–23

In this article, a two-identical-parallel-machine scheduling problem in which one machine is periodically unavailable is studied. The problem is different from that of Xu et al., ⁸ which is investigated under an uncertain scenario. Besides, there are many cases discussed in Xu et al. ⁸ The method proposed here is capable of solving the problem effectively and simplifying the proof process. Since the two-parallel-machine makespan-minimization problem without interval constraints is NP-hard, ²⁴ the problem with periodic availability constraints is also NP-hard since the conclusion that an availability constraint complicates the problem. Makespan (the latest completion time of all jobs) is usually regarded as an easy objective function for scheduling problem. However, no polynomial time approximation algorithm with constant worst-case ratio exists unless P = NP even if we assume that at least one machine is available at any time. ²⁵ In fact, some emergencies affect numerous parameters in the production scheduling process. Hence, indeterminacy should be considered by the decision maker. During the production, the processing time of the workpiece and the delivery deadline are affected by factors (e.g. the workshop environment, worker proficiency, order changes, as well as natural disasters). These values cannot be known very precisely. If there are enough historical data, these parameters could be dealt with by means of the probability theory. However, if historical data are unreliable or unavailable, we can make decisions in accordance with the uncertainty theory. Unlike the mentioned literature, the uncertainty theory is introduced into scheduling problems, making more reasonable decisions in the real world. Furthermore, if the scheduling algorithm in a deterministic scenario is still used, the optimal solution obtained may be far from the true optimal solution. Accordingly, this article proposes an effective method to solve the problem under uncertain conditions. Because of the presence of uncertainty, the worst-case ratio is worth analyzing in an uncertain scenario. Owing to the particularity of uncertain scenario, there are few relevant literature. This article attempts to provide a method to analyze the worst-case ratio in an uncertain scenario. Finally, an optimized LPT algorithm is proposed and numerical examples are used to verify its effectiveness.

The main contributions of this article are as follows. (1) The processing time of the job and the maintenance time of the machine are considered uncertain variables, which differ from that of random variables. In the reality of the shop environment, it is more reasonable to consider these factors as uncertain factors. It is considered that all jobs have two selections to be processed by machine 1 or 2, where machine 1 is not always available. (2) Due to the complexity of the uncertain scenario, the deterministic algorithm is no longer applicable, so we design a strategy to assign jobs in an uncertain scenario. The performance boundary of the LPT algorithm in an uncertain scenario is analyzed, and the setting key time instant plays an important role in the proof. (3) Based on the previous theoretical analysis, we propose an optimized LPT algorithm. Numerical experiments show that the proposed algorithm can effectively improve the optimal solution.

The rest of this article is structured as follows. In section “Preliminaries of uncertainty theory,” basic definitions and properties regarding uncertainty theory are introduced. In section “Problem description,” the uncertain parallel-machine scheduling problem periodic constraints is presented. The uncertain worst-case ratio of the LPT algorithm is obtained in section “Worst-case ratio analysis,” and an optimized LPT algorithm based on theoretical analysis is proposed. In section “Numerical experiment,” numerical experiments are performed to verify the feasibility of the proposed algorithm.

Preliminaries of uncertainty theory

Concepts about the uncertainty theory will be introduced as follows.

Let $\mathrm{\Gamma }$ be a non-empty set, and let $\mathcal{L}$ be a σ-algebra over $\mathrm{\Gamma }$ . Each element $\mathrm{\Lambda }\in \mathcal{L}$ is called an event. A set function $\mathcal{M}$ from $\mathcal{L}$ to $[0,1]$ is called an uncertain measure if it satisfies the normality axiom, duality axiom, subadditivity axiom, and product axiom:

• Axiom I (normality axiom). $\mathcal{M}\{\mathrm{\Gamma }\}=1$ for the universal set $\mathrm{\Gamma }$ ;

• Axiom II (duality axiom). $\mathcal{M}\{\mathrm{\Lambda }\}+\mathcal{M}\{{\mathrm{\Lambda }}^c\}=1$ for any event $\mathrm{\Lambda }$ ;

• Axiom III (subadditivity axiom). $\mathcal{M}\left\{\bigcup _{i=1}^{\infty }{\mathrm{\Lambda }}_i\right\}\le \sum _{i=1}^{\infty }\mathcal{M}\{{\mathrm{\Lambda }}_i\}$ for every countable sequence of events ${\mathrm{\Lambda }}_1,{\mathrm{\Lambda }}_2,\dots$ .

Besides, the product uncertain measure on the product σ-algebra $\mathcal{L}$ was defined by Liu ²⁶ as follows. Let $({\mathrm{\Gamma }}_k,{\mathcal{L}}_k,{\mathcal{M}}_k)$ be uncertainty spaces for $k=1,2,\dots$ . The product uncertain measure $\mathcal{M}$ is an uncertain measure satisfying $\mathcal{M}\left\{\underset{i=1}{\overset{\infty }{\Pi }}{\mathrm{\Lambda }}_k\right\}=\stackrel{\infty }{{\wedge }_{i=1}}{\mathcal{M}}_k\{{\mathrm{\Lambda }}_k\},$ where ${\mathrm{\Lambda }}_k$ are arbitrarily chosen events from ${\mathcal{L}}_k$ for $k=1,2,\dots$ , respectively (Product axiom).

Uncertain measure has the following two useful properties: (1) for any events ${\mathrm{\Lambda }}_1\subset {\mathrm{\Lambda }}_2$ , it yields $\mathcal{M}\{{\mathrm{\Lambda }}_1\}\le \mathcal{M}\{{\mathrm{\Lambda }}_2\}$ ; (2) for any events ${\mathrm{\Lambda }}_1$ and ${\mathrm{\Lambda }}_2$ , it yields

$$\mathcal{M}\{{\mathrm{\Lambda }}_1\}+\mathcal{M}\{{\mathrm{\Lambda }}_2\}-1\le \mathcal{M}\{{\mathrm{\Lambda }}_1\cap {\mathrm{\Lambda }}_2\}$$

(1)

The uncertain distribution $\mathrm{\Phi }$ of an uncertain variable $\xi$ is defined by $\mathrm{\Phi }(x)=\mathcal{M}\{\xi \le x\}$ for any real number $x$ . The uncertain variables ${\xi }_1,{\xi }_2,\dots ,{\xi }_m$ are said to be independent ²⁶ if

$$\mathcal{M}\{\bigcap _{i=1}^m({\xi }_i\in B_i)\}=\underset{1\le i\le m}{min}\mathcal{M}\{{\xi }_i\in B_i\}$$

for any Borel sets $B_1,B_2,\dots ,B_n$ of real numbers.

Definition 1

An uncertain variable $\xi$ on the uncertainty space $(\mathrm{\Gamma },\mathcal{L},\mathcal{M})$ is said to be (1) non-negative if $\mathcal{M}\{\xi <0\}=0$ ; and (2) positive if $\mathcal{M}\{\xi \le 0\}=0$ . ¹⁴

Let $\xi$ and $\eta$ be uncertain variables defined on the uncertainty space $(\mathrm{\Gamma },\mathcal{L},\mathcal{M})$ . We say $\xi =\eta$ if $\xi (\gamma )=\eta (\gamma )$ for almost all $\gamma \in \mathrm{\Gamma }$ . Suppose $f$ is a measurable function, and ${\xi }_1,{\xi }_2,\dots ,{\xi }_n$ are uncertain variables on $(\mathrm{\Gamma },\mathcal{L},\mathcal{M})$ . Then, $\xi =f({\xi }_1,{\xi }_2,\dots ,{\xi }_n)$ is an uncertain variable defined as $\xi (\gamma )=f({\xi }_1(\gamma ),{\xi }_2(\gamma ),\dots ,{\xi }_n(\gamma )),\forall \gamma \in \mathrm{\Gamma }$ . Let $\xi$ be an uncertain variable with continuous uncertainty distribution $\mathrm{\Phi }$ . Then, for any real number $x$ , it yields $\mathcal{M}\{\xi \le x\}=\mathrm{\Phi }(x),\mathcal{M}\{\xi \ge x\}=1-\mathrm{\Phi }(x)$ .

Example 1

An uncertain variable $\xi$ is called normal if it has a normal uncertainty distribution

$$\mathrm{\Phi }(x)={(1+\exp \left(\frac{\pi (e-x)}{\sqrt{3}\sigma }\right))}^{-1},x\in \Re$$

where $e$ and $\sigma$ are real numbers with $\sigma >0$ . The $\sigma$ is the standard deviation of normal uncertainty distribution. A normal uncertain variable $\xi$ is denoted by $\xi ~\mathcal{N}(e,\sigma )$ .

Theorem 1

Let ${\xi }_1$ and ${\xi }_2$ be independent normal uncertain variables $\mathcal{N}(e_1,{\sigma }_1)$ and $\mathcal{N}(e_2,{\sigma }_2)$ , respectively. ²⁷ ${\sigma }_1$ and ${\sigma }_2$ denote the standard deviation of normal uncertainty distribution. Then, the sum ${\xi }_1+{\xi }_2$ is also a normal uncertain variable $\mathcal{N}(e_1+e_2,{\sigma }_1+{\sigma }_2)$ , that is,

$$\mathcal{N}(e_1,{\sigma }_1)+\mathcal{N}(e_2,{\sigma }_2)=\mathcal{N}(e_1+e_2,{\sigma }_1+{\sigma }_2)$$

where ${\sigma }_1>0$ and ${\sigma }_2>0$ are real numbers. The product of a normal uncertain variable $\mathcal{N}(e,\sigma )$ and a scalar number $k>0$ is also a normal uncertain variable $\mathcal{N}(\mathrm{ke},k\sigma )$ , that is,

$$k·\mathcal{N}(e,\sigma )=\mathcal{N}(\mathrm{ke},k\sigma )$$

where $\sigma$ is a real number with $\sigma >0$ and $\sigma$ denotes the standard deviation of normal uncertainty distribution.

According to Theorem 1, the following theorem can be gotten.

Theorem 2

Assume that $\xi$ is a normal uncertain variable $\mathcal{N}(e,\sigma )$ . Then, $-\xi$ is a normal uncertain variable

$$-\mathcal{N}(e,\sigma )=\mathcal{N}(-e,\sigma )$$

Definition 2

An uncertain distribution $\mathrm{\Phi }(x)$ is said to be regular if its inverse function ${\mathrm{\Phi }}^{-1}(x)$ exists and is unique for each $\alpha \in (0,1)$ . Then, the inverse function ${\mathrm{\Phi }}^{-1}$ is called the inverse uncertainty distribution of $\xi$ . ¹⁴

Problem description

There are $n$ jobs $J_1,J_2,\dots ,J_n$ to be processed on two-identical-parallel-machine $M_1$ and $M_2$ , which are non-preemptive. All jobs are available at the beginning. Assume the machine $M_1$ is under periodic maintenance, while the machine $M_2$ is always available. The length of machine’s each availability interval is $T$ , and each maintenance time is $t$ . Each availability interval of machine $M_1$ can act as a batch. The processing time of job $J_i$ is $p_i$ for $i=1,2,\dots ,n$ . Parameters $p_1,p_2,\dots ,p_n$ and $t$ are independent of each other, of which an example is given in Figure 1. The aim is to minimize the makespan following different decision criteria.

Figure 1.

An example.

In practice, numerous parameters are affected by some emergencies. In the process of steelmaking and continuous casting, for numerous uncertain factors (e.g. machine failure, operation error, environmental impact), workers often use their own experience to assess the processing time. Given the difference in proficiency, maintenance workers can only estimate the maintenance time based on their own experience. Thus, the processing and maintenance time are considered uncertain variables following the actual scenario.

Worst-case ratio analysis

Lee ¹ considered only one unavailability interval for each machine. Nevertheless, periodic maintenance indicates that there are several unavailability periods. In such scenario, the method proposed by Lee is no longer workable. For the identical parallel-machine scheduling problem, Graham ²⁸ demonstrated that the LPT algorithm exhibits a tight worst-case ratio bound. Some relevant literatures suggested that the LPT algorithm on addressing makespan minimization problem is quite appropriate.^{5,29,30,31–35}

LPT algorithm: Sort all jobs in non-increasing order of their processing times. Each job is subsequently assigned to a machine on which it can be finished as early as possible.

Denote the optimal makespan by $C_{\mathrm{OPT}}$ and objective value of schedule produced by the LPT algorithm with $C_{\mathrm{LPT}}$ . Denote the natural number set by $\mathbb{N}$ . Rank two uncertain variables at a confidence level. That is, for two uncertain variables $\xi$ and $\eta$ and a confidence level $\alpha$ , $\xi \le \eta$ if and only if $\mathcal{M}\{\xi \le \eta \}\ge \alpha$ . Thus, it is assumed that all jobs can be sorted in a non-increasing order of their processing times at a confidence level $\alpha$ , and the LPT algorithm is used to solve the uncertain two-parallel-machine problem.

The worst-case ratio of an algorithm $H$ is defined as the smallest number $\rho$ , so $F\le \rho F^{*}$ for any instance, where $F$ and $F*$ denote the objective values of schedule produced by $H$ and the optimal schedule, respectively. Note that $\rho \ge 1$ . Set $C_H$ as the makespan obtained from algorithm $H$ , and $C_{\mathrm{OPT}}$ the optimal makespan.

Theorem 3

If two jobs are ranked by their processing times at the confidence level $\alpha$ which is more than 0.8, the uncertain worst-case ratio of the LPT algorithm is 3/2 at the confidence level $\alpha$ : $\mathcal{M}\{C_{\mathrm{LPT}}\le (3/2)C_{\mathrm{OPT}}\}\ge \alpha$ . Furthermore, the ratio 3/2 is tight.

Proof

Assume that machine $M_1$ should be maintained periodically while the machine $M_2$ is always available. It is assumed that the first maintenance starts from time instant $T$ on machine $M_1$ .

Without loss of generality, it is assumed that uncertain variables $p_1,p_2,\dots ,p_n$ and $t$ are defined on the space $\mathrm{\Gamma }$ .

Let $k$ be an uncertain variable with positive integer values satisfying

$$\frac{\sum _{i=1}^n{p}_i(\gamma )}{2T+t(\gamma )}<k(\gamma )\le \frac{\sum _{i=1}^n{p}_i(\gamma )}{2T+t(\gamma )}+1\mathrm{for}\gamma \in \mathrm{\Gamma }$$

The idea is to set a critical time instant $ϵ$ to get the relationship of $C_{\mathrm{OPT}}$ and $C_{\mathrm{LPT}}$ . Let $ϵ$ be the time instant (uncertain variable) so for $\gamma \in \mathrm{\Gamma }$

$$\begin{array}{cc}\multicolumn{1}{c}{2ϵ(\gamma )}& -(k(\gamma )-1)t(\gamma )-[\epsilon (\gamma )-k(\gamma )T\hfill \\ \multicolumn{1}{c}{}& -(k(\gamma )-1)t(\gamma ){]}^{+}=\sum _{i=1}^n{p}_i(\gamma )\hfill \end{array}$$

(2)

where “+” denotes

$$\begin{array}{c}{[ϵ(\gamma )-k(\gamma )T-(k(\gamma )-1)t(\gamma )]}^{+}\hfill \\ =\{\begin{array}{c}0,\mathrm{if}(k(\gamma )-1)(T+t(\gamma ))\le ϵ(\gamma )\le k(\gamma )T+(k(\gamma )-1)t(\gamma )\hfill \\ \multicolumn{1}{c}{ϵ(\gamma )-k(\gamma )T-(k(\gamma )-1)t(\gamma )}\\ \multicolumn{1}{c}{\mathrm{if}k(\gamma )T+(k(\gamma )-1)t(\gamma )<ϵ(\gamma )<k(\gamma )(T+t(\gamma ))}\end{array}\hfill \end{array}$$

Obviously, that $C_{\mathrm{OPT}}(\gamma )\ge ϵ(\gamma )$

$$\mathcal{M}\{C_{\mathrm{OPT}}\ge ϵ\}=1$$

(3)

For $\gamma \in \mathrm{\Gamma }$ , set $p(\gamma )=C_{\mathrm{LPT}}(\gamma )-ϵ(\gamma )$ . Because the makespan in the LPT schedule should be above or equal to the makespan in the optimal schedule, so

$$\mathcal{M}\{C_{\mathrm{LPT}}\ge C_{\mathrm{OPT}}\}=1$$

(4)

Then

$$C_{\mathrm{LPT}}\ge ϵ\}=1$$

(5)

follows from that

$$\{C_{\mathrm{LPT}}\ge ϵ\}\supseteq \{C_{\mathrm{LPT}}\ge C_{\mathrm{OPT}}\}\cap \{C_{\mathrm{OPT}}\ge ϵ\}$$

(6)

According to Definition 1, $p$ is non-negative. If

$$\mathcal{M}\{p\le \frac{1}{2}{C}_{\mathrm{OPT}}\}\ge \alpha$$

(7)

Subsequently, according to

$$\begin{array}{c}\{C_{\mathrm{LPT}}\le (3/2)C_{\mathrm{OPT}}\}\hfill \\ \multicolumn{1}{c}{\supseteq \{C_{\mathrm{LPT}}=ϵ+p\}\cap \{C_{\mathrm{OPT}}\ge ϵ\}\cap \{p\le \frac{1}{2}{C}_{\mathrm{OPT}}\}}\end{array}$$

(8)

and property (equation (1)), it yields

$$\mathcal{M}\{C_{\mathrm{LPT}}\le (3/2)C_{\mathrm{OPT}}\}\ge \alpha$$

(9)

That is, $C_{\mathrm{LPT}}\le (3/2)C_{\mathrm{OPT}}$ at the confidence level $\alpha$ . If $p$ is over $(1/2)C_{\mathrm{OPT}}$ at confidence level $\alpha$ , that is

$$\mathcal{M}\{p>\frac{1}{2}{C}_{\mathrm{OPT}}\}\ge \alpha$$

(10)

It is asserted that $C_{\mathrm{LPT}}$ and $C_{\mathrm{OPT}}$ are equal at the confidence level $\alpha$ .

Let $C_{\mathrm{LPT}}$ be the complete time $c(J_{\mathrm{last}})$ of job $J_{\mathrm{last}}$ , that is

$$\mathcal{M}\{C_{\mathrm{LPT}}=c(J_{\mathrm{last}})\}\ge \alpha$$

(11)

If the processing time $p(J_{\mathrm{last}})$ of the job $J_{\mathrm{last}}$ is above $(1/2)C_{\mathrm{OPT}}$ , that is

$$\mathcal{M}\{p(J_{\mathrm{last}})>\frac{1}{2}{C}_{\mathrm{OPT}}\}\ge \alpha$$

(12)

Then, there is not a job whose processing time is over $(1/2)C_{\mathrm{OPT}}$ except the job $J_{\mathrm{last}}$ . Otherwise, if there are more than two jobs whose processing time is above $(1/2)C_{\mathrm{OPT}}$ , at least two of these jobs will be assigned in one machine in the optimal schedule. It is assumed that jobs $J_1$ and $J_2$ are assigned in one machine and $\mathcal{M}\{p(J_1)>(1/2)C_{\mathrm{OPT}}\}\ge \alpha$ and $\mathcal{M}\{p(J_2)>(1/2)C_{\mathrm{OPT}}\}\ge \alpha$ . Since

$$\begin{array}{c}\{C_{\mathrm{OPT}}\ge p(J_1)+p(J_2)>C_{\mathrm{OPT}}\}\supseteq \{p(J_1)>\frac{1}{2}{C}_{\mathrm{OPT}}\}\hfill \\ \cap \{p(J_2)>\frac{1}{2}{C}_{\mathrm{OPT}}\}\hfill \end{array}$$

it yields

$$\begin{array}{cc}\multicolumn{1}{c}{\mathcal{M}\{C_{\mathrm{OPT}}>C_{\mathrm{OPT}}\}}& \ge \mathcal{M}\{p(J_1)>\frac{1}{2}{C}_{\mathrm{OPT}}\}\hfill \\ \multicolumn{1}{c}{}& +\mathcal{M}\{p(J_2)>\frac{1}{2}{C}_{\mathrm{OPT}}\}-1\hfill \\ \multicolumn{1}{c}{}& \ge 2\alpha -1\hfill \end{array}$$

which is a contradiction by $\mathcal{M}\{C_{\mathrm{OPT}}>C_{\mathrm{OPT}}\}=0$ .

If there are merely two jobs whose processing time is over $(1/2)C_{\mathrm{OPT}}$ (i.e. there is just one job except the job $J_{\mathrm{last}}$ , denoted by $J_1$ , whose processing time is above $(1/2)C_{\mathrm{OPT}}$ ), then in the LPT schedule they are assigned in different machines which means just one job $J_{\mathrm{last}}$ is assigned in one of the two machines. Thus

$$p(J_{\mathrm{last}})=c(J_{\mathrm{last}})$$

(13)

Subsequently

$$\mathcal{M}\{p(J_{\mathrm{last}})=C_{\mathrm{LPT}}\}\ge \alpha$$

(14)

Note that $p(J_1)$ is not less than $p(J_{\mathrm{last}})$ and not over $C_{\mathrm{LPT}}$ , that is

$$\mathcal{M}\{p(J_1)\ge p(J_{\mathrm{last}})\}\ge \alpha$$

(15)

and

$$\mathcal{M}\{p(J_1)\le C_{\mathrm{LPT}}\}\ge \alpha$$

(16)

Then, it yields

$$\mathcal{M}\{p(J_1)=C_{\mathrm{LPT}}\}\ge 3\alpha -2$$

(17)

by equation (1) and

$$\begin{array}{c}\{p(J_1)\ge p(J_{\mathrm{last}})\}\cap \{p(J_1)\le C_{\mathrm{LPT}}\}\hfill \\ \cap \{p(J_{\mathrm{last}})=C_{\mathrm{LPT}}\}\subseteq \{p(J_1)=C_{\mathrm{LPT}}\}\hfill \end{array}$$

(18)

It follows from

$$\begin{array}{c}\{p(J_1)=C_{\mathrm{LPT}}\}\cap \{p(J_{\mathrm{last}})=C_{\mathrm{LPT}}\}\subseteq \{ϵ=C_{\mathrm{LPT}}\}\hfill \\ \subseteq \{p=0\}\hfill \end{array}$$

(19)

that $\mathcal{M}\{p=0\}\ge 4\alpha -3$ , which contradicts to $\mathcal{M}\{p=0\}\le 1-\alpha$ since

$$\{p=0\}\subseteq \{p\le 0\}\subseteq \{p\le \frac{1}{2}{C}_{\mathrm{OPT}}\}$$

(20)

and

$$\mathcal{M}\{p\le \frac{1}{2}{C}_{\mathrm{OPT}}\}=1-\mathcal{M}\{p>\frac{1}{2}{C}_{\mathrm{OPT}}\}\le 1-\alpha$$

(21)

If there is only one job $J_{\mathrm{last}}$ whose processing time is above $(1/2)C_{\mathrm{OPT}}$ , then

$$C_{\mathrm{LPT}}=C_{\mathrm{OPT}}=p(J_{\mathrm{last}})$$

(22)

at the confidence level $\alpha$ .

Now let the processing time $p(J_{\mathrm{last}})$ of the job $J_{\mathrm{last}}$ be not over $(1/2)C_{\mathrm{OPT}}$ , that is

$$\mathcal{M}\{p(J_{\mathrm{last}})\le \frac{1}{2}{C}_{\mathrm{OPT}}\}\ge \alpha$$

(23)

Note that in the LPT schedule, a job with longer processing time is assigned earlier at the confidence level $\alpha$ because we rank any two jobs at the confidence level $\alpha$ . In machine $M_1$ , the total processing time $s_i$ of jobs assigned in ith batch is not less than $p(\hat{J})$ and $T-s_i$ is less than $p(\hat{J})$ if there is an assigned job (the first assigned job is denoted by $\hat{J}$ and the processing time is $p(\hat{J})$ ) in (i + 1)th batch for $i=1,2,\dots$ , that is

$$\mathcal{M}\{s_i\ge p(\hat{J})\}\ge \alpha$$

(24)

and

$$\mathcal{M}\{T-s_i<p(\hat{J})\}\ge \alpha$$

(25)

Then, it yields

$$\mathcal{M}\{T-s_i<T/2\}\ge 2\alpha -1,\mathrm{for}i=1,2,\dots$$

(26)

by

$$\begin{array}{c}\{T-s_i<T/2\}\supseteq \{s_i\ge p(\hat{J})\}\cap \hfill \\ \{T-s_i<p(\hat{J})\},i=1,2,\dots \hfill \end{array}$$

(27)

We will prove that $p(J_{\mathrm{last}})>T$ at the confidence level $\alpha$ .

Otherwise, set $\mathcal{M}\{p(J_{\mathrm{last}})\le T\}\ge \alpha$ . When $\mathcal{M}\{(k-1)(T+t)\le ϵ\le \mathrm{kT}+(k-1)t\}\ge \alpha$ , there is at least a job being assigned at the kth batch in machine $M_1$ . If there is a job to be processed after $ϵ$ in machine $M_1$ , then the kth batch is fully used before $ϵ$ and $p$ is not above the total time of unused time before previous $k-1$ batches. That is

$$\mathcal{M}\{p\le \sum _{i=1}^{k-1}(T-s_i)\}\ge \alpha$$

(28)

Since $s_i$ , $i=1,2,\dots$ are uncertain variables, it yields

$$\begin{array}{c}\mathcal{M}\left\{\bigcap _{i=1}^{k-1}\{T-s_i<T/2\}\right\}\hfill \\ =\underset{1\le i\le k-1}{min}\mathcal{M}\{T-s_i<T/2\}\ge 2\alpha -1\hfill \end{array}$$

(29)

It follows from

$$\begin{array}{cc}\multicolumn{1}{c}{\{p\le \sum _{i=1}^{k-1}(T-s_i)\}}& \bigcap \left\{\bigcap _{i=1}^{k-1}\{T-s_i<T/2\}\right\}\hfill \\ \multicolumn{1}{c}{}& \subseteq \{p<(k-1)T/2\}\hfill \end{array}$$

(30)

that

$$\mathcal{M}\{p<(k-1)T/2\}\ge 3\alpha -2$$

(31)

On the contrary, since

$$\begin{array}{c}\{p>\frac{1}{2}{C}_{\mathrm{OPT}}\}\cap \{C_{\mathrm{OPT}}\ge ϵ\}\cap \{ϵ\ge (k-1)(T+t)\}\hfill \\ \subseteq \{p>(k-1)(T+t)/2\}\hfill \end{array}$$

(32)

and

$$\{p>(k-1)(T+t)/2\}\subseteq \{p>(k-1)T/2\}$$

(33)

it yields

$$\mathcal{M}\{p>(k-1)T/2\}\ge 2\alpha -1$$

(34)

By Axiom II of uncertain measure, it yields

$$\begin{array}{cc}\multicolumn{1}{c}{1}& \ge \mathcal{M}\{p<(k-1)T/2\}+\mathcal{M}\{p>(k-1)T/2\}\hfill \\ \multicolumn{1}{c}{}& \ge (3\alpha -2)+(2\alpha -1)>1\hfill \end{array}$$

(35)

which is a contradiction.

If the last job in machine $M_1$ is completed before $ϵ$ , then

$$\mathcal{M}\{p\le \sum _{i=1}^{k-1}(T-s_i)+ϵ-(k-1)(T+t)-s_k\}\ge \alpha$$

(36)

or

$$\mathcal{M}\{p\le \sum _{i=1}^k(T-s_i)+ϵ-(k-1)(T+t)-T\}\ge \alpha$$

(37)

Note that $\mathcal{M}\{p(J_{\mathrm{last}})\le s_k\}\ge \alpha$ and $\mathcal{M}\{p(J_{\mathrm{last}})>T-s_k\}\ge \alpha$ . Thus

$$\mathcal{M}\{s_k>\frac{1}{2}T\}\ge 2\alpha -1$$

(38)

or

$$\mathcal{M}\{T-s_k<\frac{1}{2}T\}\ge 2\alpha -1$$

(39)

By equation (1), the conclusion

$$\mathcal{M}\{ϵ>\mathrm{kT}+(k-1)t\}\ge 4\alpha -3$$

(40)

follows from

$$\begin{array}{c}\{p\le \sum _{i=1}^k(T-s_i)+ϵ-(k-1)(T+t)-T\}\hfill \\ \bigcap \{p>C_{\mathrm{OPT}}/2\}\bigcap \{C_{\mathrm{OPT}}\ge ϵ\}\bigcap \left\{\bigcap _{i=1}^k\{T-s_i<T/2\}\right\}\hfill \\ \subseteq \{ϵ>\mathrm{kT}+(k-1)t\}\hfill \end{array}$$

and

$$\begin{array}{c}\mathcal{M}\left\{\bigcap _{i=1}^k\{T-s_i<T/2\}\right\}\hfill \\ =\underset{1\le i\le k}{min}\mathcal{M}\{T-s_i<T/2\}\ge 2\alpha -1\hfill \end{array}$$

(41)

By Axiom II of uncertain measure, it yields

$$\begin{array}{c}1\ge \mathcal{M}\{(k-1)(T+t)\le ϵ\le \mathrm{kT}+(k-1)t\}\hfill \\ +\mathcal{M}\{ϵ>\mathrm{kT}+(k-1)t\}\ge \alpha +4\alpha -3>1\hfill \end{array}$$

(42)

which is a contradiction.

When $\mathcal{M}\{\mathrm{kT}+(k-1)t\le ϵ\le k(T+t)\}\ge \alpha$ , it yields

$$\mathcal{M}\{p\le \sum _{i=1}^k(T-s_i)\}\ge \alpha$$

(43)

It follows from

$$\begin{array}{c}\{p\le \mathrm{kT}/2\}\hfill \\ \supseteq \{p\le \sum _{i=1}^k(T-s_i)\}\bigcap \left\{\bigcap _{i=1}^k\{T-s_i<T/2\}\right\}\hfill \end{array}$$

(44)

and equation (41) that

$$\mathcal{M}\{p\le \mathrm{kT}/2\}\ge 3\alpha -2$$

(45)

On the contrary, it yields

$$\mathcal{M}\{p>(\mathrm{kT}+(k-1)t)/2\}\ge 2\alpha -1$$

(46)

by

$$\begin{array}{c}\{p>(\mathrm{kT}+(k-1)t)/2\}\supseteq \{p>C_{\mathrm{OPT}}/2\}\cap \{C_{\mathrm{OPT}}\ge ϵ\}\hfill \\ \cap \{ϵ\ge \mathrm{kT}+(k-1)t\}\hfill \end{array}$$

(47)

By Axiom II of uncertain measure, it yields

$$\begin{array}{c}1\ge \mathcal{M}\{p\le \mathrm{kT}/2\}+\mathcal{M}\{p>(\mathrm{kT}+(k-1)t)/2\}\hfill \\ \ge 3\alpha -2+2\alpha -1>1\hfill \end{array}$$

(48)

which is a contradiction.

Accordingly,

$$\mathcal{M}\{p(J_{\mathrm{last}})>T\}\ge \alpha$$

(49)

Processing time of jobs before $J_{\mathrm{last}}$ are all over $T$ . That is to say, all jobs with processing time above $T$ are assigned in machine $M_2$ and other jobs are assigned in machine $M_1$ . Accordingly, $C_{\mathrm{LPT}}$ and $C_{\mathrm{OPT}}$ are equal at the confidence level $\alpha$ .

In a word, the uncertain worst-case ratio of the LPT algorithm is 3/2 at the confidence level $\alpha$ .

To confirm that the uncertain worst-case ratio of the LPT algorithm is tight, we give an example.

For a positive integer $m$ , let

$$T=2m-2,t~\mathcal{N}(m,\sigma )\mathrm{in}\mathrm{machine}{M}_1$$

and

$$\begin{array}{c}{p}_1~\mathcal{N}(m+1,\sigma ),p_2~\mathcal{N}(m,\sigma ),\hfill \\ p_3~\mathcal{N}(m-1,\sigma ),p_4~\mathcal{N}(m-2,\sigma )\hfill \end{array}$$

where

$$\sigma =\frac{\pi }{4\sqrt{3}\ln 3}$$

Take α = 0.9.

According to Theorems 1 and 2, it yields $p_2-p_1~\mathcal{N}(-1,2\sigma )$ . According to the definition of uncertainty distribution, it yields

$$\begin{array}{cc}\multicolumn{1}{c}{\mathcal{M}\{p_1\ge p_2\}}& =\mathcal{M}\{p_2-p_1\le 0\}\hfill \\ \multicolumn{1}{c}{}& ={(1+\exp \left(\frac{-\pi }{2\sqrt{3}\sigma }\right))}^{-1}\hfill \\ \multicolumn{1}{c}{}& =0.9\hfill \end{array}$$

By the same method, we can get the uncertainty distributions of $p_3-p_2$ and $p_4-p_3$ , then

$$\begin{array}{c}\multicolumn{1}{c}{\mathcal{M}\{p_2\ge p_3\}=\mathcal{M}\{p_3\ge p_4\}={(1+\exp \left(\frac{-\pi }{2\sqrt{3}\sigma }\right))}^{-1}}\\ \multicolumn{1}{c}{=0.9}\end{array}$$

Thus, jobs are sorted as $J_1,J_2,J_3,J_4$ in non-increasing order of the processing time at the confidence level 0.9.

According to Theorems 1 and 2, it yields

$$p_1+p_2~\mathcal{N}(2m+1,2\sigma ),p_1+p_2-T~\mathcal{N}(3,2\sigma )$$

Then, it yields

$$\mathcal{M}\{p_1+p_2\le T\}={(1+\exp \left(\frac{3\pi }{2\sqrt{3}\sigma }\right))}^{-1}=0.00137$$

So, jobs $J_1$ and $J_2$ cannot be assigned to the first batch of machine $M_1$ synchronously. By the same method, we can get the uncertainty distributions of $p_1+p_3-T$ , $p_1+p_4-T$ , $p_2+p_3-T$ , $p_2+p_4-T$ , and $p_2+p_3-(T+t)$ . Then, it yields

$$\begin{array}{c}\mathcal{M}\{p_1+p_3\le T\}={(1+\exp \left(\frac{2\pi }{2\sqrt{3}\sigma }\right))}^{-1}=0.0122\hfill \\ \mathcal{M}\{p_1+p_4\le T\}={(1+\exp \left(\frac{\pi }{2\sqrt{3}\sigma }\right))}^{-1}=0.1\hfill \\ \mathcal{M}\{p_2+p_3\le T\}={(1+\exp \left(\frac{\pi }{2\sqrt{3}\sigma }\right))}^{-1}=0.1\hfill \\ \mathcal{M}\{p_2+p_4\le T\}={(1+\exp (0))}^{-1}=0.5\hfill \\ \mathcal{M}\{p_2+p_3\le T+t\}={(1+\exp \left(\frac{(1-m)\pi }{3\sqrt{3}\sigma }\right))}^{-1}\hfill \\ ={(1+{(1/9)}^{\frac{2(m-1)}{3}})}^{-1}>0.9\hfill \end{array}$$

According to the LPT algorithm, job $J_1$ is assigned to the first batch of machine $M_1$ . Subsequently, jobs $J_2$ and $J_3$ will be assigned to machine $M_2$ in sequence.

According to Theorems 1 and 2, it yields

$$p_1+p_4~\mathcal{N}(2m-1,2\sigma ),p_1+p_4-T~\mathcal{N}(1,2\sigma )$$

Then, it yields

$$\mathcal{M}\{p_1+p_4\le T\}={(1+\exp \left(\frac{\pi }{2\sqrt{3}\sigma }\right))}^{-1}=0.1$$

According to Theorems 1 and 2, it yields

$$\begin{array}{c}{p}_2+p_3~\mathcal{N}(2m-1,2\sigma ),\hfill \\ p_2+p_3-T-t~\mathcal{N}(-m+1,3\sigma )\hfill \end{array}$$

Consequently

$$\begin{array}{cc}\multicolumn{1}{c}{\mathcal{M}\{p_2+p_3\le T+t\}}& ={(1+\exp \left(\frac{\pi (-m+1)}{3\sqrt{3}\sigma }\right))}^{-1}\hfill \\ \multicolumn{1}{c}{}& ={(1+{(1/9)}^{\frac{2(m-1)}{3}})}^{-1}>0.9\hfill \end{array}$$

Hence

$$C_{\mathrm{LPT}}=p_2+p_3+p_4$$

According to Theorems 1 and 2, it yields

$$\begin{array}{c}{p}_3+p_4~\mathcal{N}(2m-3,2\sigma ),\hfill \\ p_3+p_4-T-t~\mathcal{N}(-m-1,3\sigma )\hfill \end{array}$$

Then, it yields

$$\begin{array}{cc}\multicolumn{1}{c}{\mathcal{M}\{p_3+p_4}& \le T\}=\mathcal{M}\{p_3+p_4-T\le 0\}\hfill \\ \multicolumn{1}{c}{}& ={(1+\exp \left(\frac{-\pi }{2\sqrt{3}\sigma }\right))}^{-1}=0.9\hfill \end{array}$$

The optimal schedule assigns $J_3$ and $J_4$ to machine $M_1$ and assigns $J_1$ and $J_2$ to machine $M_2$ . It yields

$$C_{\mathrm{OPT}}=p_1+p_2$$

For $1\le \rho \le 2$ , and according to Theorems 1 and 2 it follows from

$$\begin{array}{c}-\rho p_1-(\rho -1)p_2+p_3+p_4~\mathcal{N}(3m-(2m+1)\rho -3,\hfill \\ (2\rho +1)\sigma )\hfill \end{array}$$

that

$$\begin{array}{cc}\multicolumn{1}{c}{\mathcal{M}\{C_{\mathrm{LPT}}}& \le \rho C_{\mathrm{OPT}}\}=\mathcal{M}\{p_2+p_3+p_4\le \rho p_1+\rho p_2\}\hfill \\ \multicolumn{1}{c}{}& =\mathcal{M}\{-\rho p_1-(\rho -1)p_2+p_3+p_4\le 0\}\hfill \\ \multicolumn{1}{c}{}& ={(1+\exp \left(\frac{3m-(2m+1)\rho -3}{(2\rho +1)\sqrt{3}\sigma }\pi \right))}^{-1}\hfill \end{array}$$

It follows from

$$\mathcal{M}\{C_{\mathrm{LPT}}\le \rho C_{\mathrm{OPT}}\}=\alpha =0.9$$

that

$$\rho =\frac{3m+\frac{\sqrt{3}\sigma }{\pi }\ln 9-3}{2m-\frac{2\sqrt{3}\sigma }{\pi }\ln 9+1}$$

which converges to 3/2 as $m\to \infty$ . This indicates that the uncertain worst-case ratio 3/2 is tight. The proof is completed.

Remark 1

The condition that $\alpha$ is over 0.8 is sufficient for Theorem 3. If $\alpha$ is below $0.8$ , the required result may not be deduced based on the current method in the proof of Theorem 3. Also, $\alpha$ above $0.8$ suggests that our conclusion holds at a high confidence level. It is reasonable since the scenario that a result holds at a lower confidence level in reality is not considered on the whole.

According to Theorem 3, the LPT Algorithm is modified.

Improved longest processing time algorithm (ILPT):

• Step 1. Array jobs in descending order of processing time at the confidence level $\alpha$ .

• Step 2. The jobs are arranged according to LPT. When a new job cannot be added in machine 1, the last job (which has the shortest processing time) is arranged in the current batch.

• Step 3. Repeat Step 2 until all the jobs are arranged.

Since the gap of each batch is less than that of LPT, ILPT obviously outperforms LPT.

Numerical experiment

To assess the performance of the ILPT algorithm, numerical experiments are performed.

The average-case error (AE) is a vital measure to assess the performance of the algorithm. It is expressed as

$$\mathrm{AE}=\sum \frac{(C-C*)}{C*}\times \frac{1}{N}$$

where $C*$ denotes the optimal schedule; $C$ represents the objective function value obtained from an algorithm; $N$ is the cardinal number of the testing problem.

LS may indicate any greedy method that schedules jobs according to a given priority list. As a matter of fact, LPT can be considered a particular case of LS where the priority list is ordered according to job processing times. Table 1 lists the numerical results of the three algorithms.

Table 1.

Average-case error.

N	$\mathrm{A}{\mathrm{E}}_{\mathrm{LPT}}$	$\mathrm{A}{\mathrm{E}}_{\mathrm{LS}}$	$\mathrm{A}{\mathrm{E}}_{\mathrm{ILPT}}$
50	0.0022	0.0182	0.0013
100	0.0013	0.0113	0.0009
200	0.0007	0.0069	0.0004
500	0.0002	0.0034	0.0001
800	0.0001	0.0016	0.0000
1000	0.0000	0.0009	0.0000
2000	0.0000	0.0005	0.0000
5000	0.0000	0.0002	0.0000

The result reveals that the performances of the three algorithms are being enhanced with the increase in the number of jobs. Besides, in all cases, the performance of the ILPT is superior to the other two algorithms.

Conclusion

In this article, a two-parallel-machine scheduling problem with periodic maintenance was studied. For the existence of non-deterministic phenomena in practice, processing and maintenance time were considered uncertain variables, which is not consistent with problems studied in existing literature. The worst-case ratio of the LPT algorithm under the uncertain scenario was obtained. To analyze the uncertain two-parallel-machine scheduling problem, jobs are sorted by uncertain measure at a relatively high confidence level $\alpha$ which is over $0.8$ . A novel method that relies on uncertain measure and confidence level was proposed. Results suggested that the worst-case ratio of the algorithm is 3/2 at a relatively high confidence level. Numerical experiment results suggested that the performance of the ILPT algorithm is relatively satisfactory.

For subsequent work, some efficient exact algorithms are worth developing to solve these problems with periodic maintenance. Considerable additional factors (e.g. setup time, due date, and transport time) can be considered uncertain variables. Flow shop, job shop, and open shop problems will be considered. Other performance measures (e.g. total completion time or mean flow time) will be considered as well.