International Journal of Computational Intelligence Systems

Volume 13, Issue 1, 2020, Pages 193 - 200

A Single Machine Scheduling with Periodic Maintenance and Uncertain Processing Time

Authors
Jiayu Shen1, *, Yuanguo Zhu2
1Department of Public Basic Courses, Nanjing Institute of Industry Technology, Nanjing 210023, Jiangsu, People's Republic of China
2School of Science, Nanjing University of Science and Technology, Nanjing 210094, Jiangsu, People's Republic of China
*Corresponding author. Email: fjcyue007@126.com
Corresponding Author
Jiayu Shen
Received 19 April 2019, Accepted 13 February 2020, Available Online 23 February 2020.
DOI
10.2991/ijcis.d.200214.003How to use a DOI?
Keywords
Single machine; Periodic maintenance; Uncertainty; Chance-constrained; Genetic algorithm
Abstract

A single machine scheduling problem with periodic maintenance is studied in this paper. Due to many uncertainties in reality, the processing time is recognized as an uncertain variable. The aim is to minimize the makespan at a confidence level. An uncertain chance-constrained programming model is developed to delve into the impact of uncertainties on decision variables, and an algorithm for calculating the objective function is proposed. According to the theoretical analysis, a novel method named longest shortest processing time (LSPT) rule is proposed. Subsequently, an improved genetic algorithm (GA-M) combined with LSPT rule is proposed. Numerical experiments are used to verify the feasibility of this model and algorithm.

Copyright
© 2020 The Authors. Published by Atlantis Press SARL.
Open Access
This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

1. INTRODUCTION

Most studies on scheduling problems assume that the machine is always available. However, this assumption does not hold in reality. If the machine runs constantly, it is prone to failure. To reduce the wastage and expand life expectancy of a machine, preventive maintenance activities are essential. During the process of maintenance, jobs need to stop and wait. This is due to a lack of coordination between job scheduling and machine maintenance. The purpose of this study is to coordinate their relationship.

The machine maintenance is often treated as an unavailability interval in the literature. Lee [1] studied several scheduling problems where each machine has only one unavailability interval, and carried out theoretical analysis under each scenario. Low et al. [2] studied a single machine scheduling problems with availability constraints, and a flexible model and heuristic algorithms were proposed. Lee and Kim [3] considered a single machine scheduling problem with periodic maintenance and a two-phase heuristic algorithm modified from Moore's algorithm was developed. A single machine scheduling problem with periodic maintenance was studied by Benmansour et al. [4], and two mixed integer linear models were developed. Four single-machine scheduling problems with a variable machine maintenance were investigated by Ying et al. [5] and polynomial-time exact algorithms were proposed. A single machine scheduling problem with flexible periodic maintenances was studied by Cui and Lu [6], and an effective heuristic was developed to solve the non-resumable case. Two machine-related periodic maintenance scheduling models were established by Li et al. [7], and two improved heuristic algorithms were proposed. A single machine scheduling problem with periodic maintenance and sequence-dependent set-up times was analyzed by Pacheco et al. [8], and an efficient variable neighborhood search approach with memory was proposed. Nesello et al. [9] proposed new arc-time index formulations for scheduling with periodic maintenances and given a simple iterative exact algorithm. Perez-Gonzalez and Framinan [10] developed single machine scheduling models with cyclical machine availability periods, and proposed new heuristics based on bin packing assignment rules. Wang et al. [11] studied a single machine scheduling problem with deteriorating jobs and flexible periodic maintenance. Two integer programming formulations and a branch-and-price algorithm were proposed.

Most of the mentioned scheduling problems were investigated in a deterministic scenario. Since human behaviors are involved in the process, the decision maker has to take into account all of the possible events during the planning horizon. Frequency is a factual property of indeterminate quantity and does not change with our state of knowledge and preference. When the sample size is large enough and no emergency (e.g. war, flood, earthquake, accident and even rumor) arises, it is likely for us to find a distribution function that is sufficiently close enough to the frequency. In this case, the probability theory is undoubtedly the only legitimate method to address our problem. But, when statistics are unreliable or unavailable, probability theory is not the best choice. Due to the absence of data for these variables, experts should be invited to assess the belief degree that an uncertain event will occur. To deal with the involved human uncertainty, the uncertainty theory was founded by Liu [12] in 2007 and refined it in 2010 [13]. The uncertainty theory is a branch of axiomatic mathematics for modeling human uncertainty, which has been deeply developed in many fields such as uncertain programming [1416], uncertain scheduling [1722], uncertain risk analysis [2325], uncertain calculus [2628] and uncertain optimal control [2934].

In this paper, a single machine scheduling problem with periodic maintenance and non-preemptive jobs is studied. There are many uncertainties in the real workshop environment, which cannot be described by random variables. For example, in mold processing, due to machine failures, operational errors, order changes and many other uncertainties, workers usually draw on their past experience to assess the processing time. Therefore, the processing time is considered an uncertain variable owing to the lack of historical data. To address uncertain variables in the problem, a chance-constrained model is established. The aim is to minimize the makespan at a pre-given confidence level. The equivalent form of the uncertain model is obtained in accordance with uncertainty theory. Accordingly, a new algorithm for solving the objective function is proposed. Furthermore, to improve the efficiency of solving the model, an improved genetic algorithm (GA-M) combined with longest shortest processing time (LSPT) rule is proposed. Numerical experiments are made to verify the feasibility of the proposed model and methods.

The rest of this paper is structured as follows. In Section 2, basic definitions and properties about uncertainty theory are introduced. In Section 3, we analyze the problem under an uncertain scenario and built a chance-constrained model. Besides, according to the dominating property, an algorithm is proposed to calculate the objective function. In Section 4, an evolutionary algorithm base on the genetic algorithm (GA) is proposed. In Section 5, numerical experiments are given.

2. PRELIMINARIES OF UNCERTAINTY THEORY

The uncertainty theory is founded by Liu [12] in 2007 and refined by Liu [13] in 2010 as a branch of axiomatic mathematics for modeling human uncertainty. Let Γ be a nonempty set, a σ-algebra over Γ and each element Λ in is called an event. Uncertain measure is defined as a function from to [0, 1]. In detail, Liu [12] gives the concept of uncertain measure as follows:

A set function from to [0,1] is called an uncertain measure if it satisfies {Γ}=1 for the universal set Γ; {Λ}+{Λc}=1 for any event Λ; i=1Λii=1{Λi} for every countable sequence of events Λ1,Λ2,.

Besides, the product uncertain measure on the product σ-algebra was defined by Liu [35] as follows: Let (Γk,k,k) be uncertainty spaces for k=1,2, . The product uncertain measure is an uncertain measure satisfying i=1Λk=i=1k{Λk}, where Λk are arbitrarily chosen events from k for k=1,2, , respectively. Uncertain measure has following two useful properties: (i) for any events Λ1Λ2, we have {Λ1}{Λ2}; (ii) for any events Λ1 and Λ2, we have

{Λ1}+{Λ2}1{Λ1Λ2}{Λ1}{Λ2}.(1)

The uncertain distribution Φ of an uncertain variable ξ is defined by Φ(x)={ξx} for any real number x. Let ξ be an uncertain variable with continuous uncertainty distribution Φ. Then for any real number x, we have {ξx}=Φ(x), {ξx}=1Φ(x).

The uncertain variables ξ1,ξ2,,ξm are said to be independent (Liu [35]) if

i=1m(ξiBi)=min1im{ξiBi}
for any Borel sets B1,B2,,Bn of real numbers.

Example 1.

An uncertain variable ξ is called normal if it has a normal uncertainty distribution

Φ(x)=1+expπ(ex)3σ1,x
denoted by N(e,σ) where e and σ are real numbers with σ>0.

Definition 1.

[12] An uncertain distribution Φ(x) is said to be regular if its inverse function Φ1(x) exists and is unique for each α(0,1). Then the inverse function Φ1 is called the inverse uncertainty distribution of ξ.

Example 2.

The inverse uncertainty distribution of normal uncertain variable N(e,σ) is

Φ1(α)=e+σ3πlnα1α.

Theorem 1.

[13] Let ξ1,ξ2,,ξn be independent regular uncertain variables with uncertainty distributions Φ1,Φ2,,Φn, respectively. If function f(x1,,xm,xm+1,,xn) is strictly increasing with respect to x1,x2,,xm, and strictly decreasing with respect to xm+1,xm+2,,xn, then

ξ=f(ξ1,ξ2,,ξn)
is an uncertain variable with inverse uncertainty distribution
Ψ1(α)=f(Φ11(α),,Φm1(α),Φm+11(1α),,Φn1(1α)).

Definition 2.

[13] Let ξ1 and ξ2 be independent normal uncertain variables N(e1,σ1) and N(e2,σ2), respectively. σ1 and σ2 denote the standard deviation of normal uncertainty distribution. Then the sum ξ1+ξ2 is also a normal uncertain variable N(e1+e2,σ1+σ2), i.e.,

N(e1,σ1)+N(e2,σ2)=N(e1+e2,σ1+σ2),
where σ1>0 and σ2>0 are real numbers. The product of a normal uncertain variable N(e,σ) and a scalar number k>0 is also a normal uncertain variable N(ke,kσ), i.e.,
kN(e,σ)=N(ke,kσ),
where σ is a real number with σ>0 and σ denotes the standard deviation of normal uncertainty distribution.

Definition 3.

[12] Let ξ be an uncertain variable, and α(0,1]. Then

ξsup(α)=sup{r~{ξr}α}
is called the optimistic value to ξ, and
ξinf(α)=inf{r{ξr}α}
is called the pessimistic value to ξ.

Uncertain programming is a type of mathematical programming involving uncertain variables. Assume that x is a decision vector, ξ is an uncertain vector, f(x,ξ) is an objective function, and gj(x,ξ) are constraint functions, j=1,2,,p. To obtain a decision with minimum objective value subject to chance constraints, Liu [36] proposed the following uncertain programming model.

minxf̄subject to:{f(x,ξ)f̄}β{gj(x,ξ)0}αj,j=1,2,,p,
where αj and β are specified confidence levels for j=1,2,,p, and minf¯ is the pessimistic value.

A key problem is how to solve the above model. Under the framework of uncertainty theory, an uncertain programming model can be transformed into a crisp one if the related functions are monotone [13].

3. MODEL UNDER UNCERTAIN ENVIRONMENT

There are n independent non-resumable jobs J1,J2, ,Jn to be processed on a single machine. The processing time of job Ji is ξi. Let the length of each availability interval be T and the length of each maintenance interval be t. max1inξiT, otherwise there is trivially no feasible schedule. Moreover, the machine is available at time zero. The processing time of a job is often considered a deterministic parameter in the literature. In fact, the processing time has a great relationship with the experience of workers who assess approximate time based on personal experience. Therefore, it is reasonable to treat the processing time of a job as an uncertain variable. Since the uncertain variables cannot be directly compared in size, we rank them at a confidence level. ξη if and only if {ξη}α for two uncertain variables ξ, η and a confidence level α. According to the definition of uncertainty distribution, we have Φξη(0)α, where Φξη denotes the uncertainty distribution of ξη. Without loss of generality, assume that M availability intervals are used. The objective function is

f=(M1)(T+t)+SumM,(2)
where SumM denotes the total processing time of jobs at the Mth availability interval.

In practice, the decision maker always consider the impact of risks and emergencies, and find a boundary as a reference for the optimal schedule. In this scenario, the concept of chance-constrained [37] can be adopted to address this problem. The decision maker has to assess a value in advance, such that there exists an optimistic solution x satisfying {f(x)f¯}α, where α(0,1) is a predetermined confidence level. For instance, set α=0.9, the decision maker needs to determine a target f¯ and search a solution x to satisfy {f(x)f¯}0.9. This suggests that if the decision maker takes a solution x, the target aim value should be less than f¯ with confidence level at least 90 %.

It is noted that the aim of this paper is to minimize makespan at a pre-given confidence level, which means to find the supremum of the maximum completion time (makespan). It corresponds to the definition of pessimism value (Definition 3). Therefore, we build a chance-constrained model in the sense of pessimism.

minxf¯subject to:{ff¯}α,(3)
where x denotes the order of jobs and it is the decision variable.

According to the definition of the pessimistic value (Definition 3), the model is equivalent to a crisp one. The equivalent objective function is:

minxΨf1(α),(4)
where the Ψf1 denotes the inverse uncertainty distribution of f.

According to Theorem 1, it yields

Ψf1(α)=(M1)(T+t)+ΦSumM1(α).(5)

Likewise, to obtain the value of Ψf1(α), we should calculate values of ΦSumM1(α) and (M1)(T+t). Note that we need to know which jobs in the last occupied availability interval and how many availability intervals are occupied. It indicates that how to obtain the value of M and which jobs in the last availability interval are two critical problems. Subsequently, an algorithm named Algorithm 1 for the two critical problems is proposed. Since the decision variable is the order of jobs, the order of the jobs has been drawn after using heuristic algorithms. The order is ξi1,ξi2,,ξin.

Algorithm 1:

  • Start to inspect from the first available interval. Because each availability interval can accommodate at least one job, we take turns to examine whether the following conditions can be satisfied: {ξi1+ξi2T}α, {ξi1+ξi2+ξi3T}α, …, {ξi1+ξi2+ξi3++ξinT}α.

    If all of the above n1 conditions are satisfied, we have M=1.

    If {ξi1+ξi2T}α,,{ξi1+ξi2++ξijT}α, {ξi1+ξi2++ξij+ξij+1T}<α, then assign jobs Ji1,,Jij to the first available interval. It indicates that these jobs will be processed in the first available interval.

  • Repeat the above operation on the remaining jobs Jij+1,,Jin from the following available intervals until all jobs are arranged to available intervals. Finally, we can know which jobs in the last availability interval and obtain the value of M.

A dominant property for two adjacent jobs (i and j) is derived. The processing time of the two jobs are ξi and ξj. Let I and I be two schedules where the difference between I and I is a pairwise interchange of jobs i and j, i.e., I=(πijπ) and I=(πjiπ) where π and π denote the partial sequences. Let Cmax and Cmax denote the makespan of schedule I and I, respectively. If job i and j are in the same interval, the exchange of their location has no effect on the makespan. We just need to consider them in different intervals. In schedule I, job i and j are in kth and (k+1)th available interval, respectively. Assume that total processing time of jobs in the kth and (k+1)th available interval are A and B, respectively. α is a given confidence level.

Three scenarios for the relationship between job i and j are shown below.

  1. {ξi>ξj}α. After exchanging the position of job i and j, there are two cases.

    • {Bξj+ξi>T}α. Since

      {CmaxCmax}{ξi>ξj}{Bξj+ξi>T},
      it yields
      {CmaxCmax}{ξi>ξj}+{Bξj+ξi>T}12α1
      by Eq. (1).

    • {Bξj+ξiT}α. Since

      {Cmax=Cmax}{ξi>ξj}{Bξj+ξiT},
      it yields {Cmax=Cmax}2α1.

  2. {ξi=ξj}α. After exchanging the position of job i and j, it yields

    {Cmax=Cmax}α
    because {Cmax=Cmax}{ξi=ξj}.

  3. {ξi<ξj}α. After exchanging the position of job i and j, there are two cases.

    • {Aξi+ξj>T}α, then job i and j are at the same available interval. If {B+ξiT}α, and according to

      {CmaxCmax}{ξi<ξj}{Aξi+ξj>T}{B+ξiT}
      it yields {CmaxCmax}3α2.

      If {B+ξi<T}α, we have

      {Cmax=Cmax}3α2.

    • {Aξi+ξjT}α. Since

      {CmaxCmax}{Bξj+ξiT}{ξi<ξj}{Aξi+ξjT},
      it yields {CmaxCmax}2α1.

Based on the above discussion, a domination property under an uncertain scenario can be deduced.

Property 1.

In schedule I, for two adjacent job i and j, if {ξi<ξj}α and {Aξi+ξjT}α, then schedule I is better than schedule I under confidence level 2α1, where α is a given confidence level.

4. HEURISTIC METHOD

The longest processing time (LPT) rule is often used to solve the scheduling problem with minimal makespan [6,3841]. The shortest processing time (SPT) rule is often used to solve the scheduling problem with minimal the total completion time [4245].

The LPT and SPT rules are described as follows:

LPT: Reorder all the jobs in non-increasing order of their processing times, and process them consecutively as early as possible.

SPT: Reorder all the jobs in non-decreasing order of their processing times, and process them consecutively as early as possible.

After integrating LPT and SPT, the LSPT rule is described as follows:

First, we sort the jobs in descending order of processing time. Then, the jobs are arranged to the first available interval in sequence. The first two steps are to arrange the jobs according to the LPT rule. If the remaining space of the first available interval cannot arrange jobs in accordance with LPT rule, then arrange the jobs with the shortest processing time in the remaining interval of the first available interval. If there is still a free position in the first available interval, continue to arrange the jobs in ascending order of processing time. The next two steps are similar to the SPT rule. In each subsequent available interval, first use the LPT rule to arrange the jobs. If the remaining space cannot continue to arrange them, use the SPT rule. Each available interval is arranged in this way until all the jobs are arranged.

The main idea of the LSPT rule is to make the total processing time of jobs within a availability interval close to T as far as possible. Therefore, LSPT rule is better than that of LPT rule.

The GA had been widely used for solving scheduling problems in recent years [4650]. It has been proven to be suitable for different types of scheduling problems, and various improved GAs had been proposed to speed up the convergence speed and reduce errors. In general, the initial solutions are randomly generated in GA, which reduces the execution efficiency of the algorithm. Some literature have shown that the better solution can be found quickly by seeding the initial solution with heuristic rules in an artificial intelligence algorithm [5153]. Therefore, we use the LSPT rule and Property 1 improve accuracy and efficiency of the initial solution. An improved algorithm named GA-M is proposed.

Algorithm GA-M:

  • Step 1: Representation

    The algorithm imitates the process of natural evolution in a population of chromosomes with the objective of largely preserving those individuals who are most adaptive to the environment. The chromosome is constructed based on a n character string [a1,a2,,an], where ai denotes the index of job i. It represents the sequence of jobs on the machine. This encoding means that any solution is feasible.

  • Step 2: Initialization

    Let the population size be pop_size, and the crossover probability be Pc and the mutation probability be Pm. The LSPT rule is used to obtain an initial chromosome. Since the processing time of each job is an uncertain variable, jobs cannot be sorted directly based on the processing times. We may sort jobs according to Φξi1(α) which is the inverse uncertainty distribution of ξi and α is a given confidence level. The other chromosomes are randomly generated by exchanging two genes of the initial chromosome. Repeat this process for pop_size1 times and we obtain pop_size chromosomes. The Property 1 is used to adjust the initial solution. After the initial solution is generated, determine whether the initial solution satisfies property 1. If the condition of Property 1 is satisfied, the position of the two adjacent jobs are exchanged.

  • Step 3: Fitness

    The fitness of an individual is defined as the possibility that an individual is likely to stay during the selection process. The objective functions of all chromosomes are calculated as their fitness values. Algorithm 1 is the key to obtain the value of the objective function.

  • Step 4: Selection process

    Chromosomes are selected by spinning the roulette wheel. These percentage fitness values can be used to configure roulette. Each time the wheel stops this gives the fitter individuals the greatest chance of being selected for the next generation and subsequent mating pool.

  • Step 5: Crossover

    The crossover operation uses two-point crossover method: two crossover point are selected, binary string from beginning of chromosome to the first crossover point is copied from one parent, the part from the first to the second crossover point is copied from the second parent and the rest is copied from the first parent. Select two chromosomes randomly and generate a random number rc. If rc is smaller than Pc, then crossover is applied to this pair; otherwise, no crossover is performed.

  • Step 6: Mutation

    The purpose of mutation operation is to maintain diversity in the population as well as to prevent the seek process from getting fall into a local optima. The mutation operation selects two positions in a chromosome randomly and interchange the two positions. In the mutation step, two chromosomes are randomly selected and a random number rm is generated first. If rm is smaller than Pm, then mutation is applied to this pair; otherwise, no mutation is performed.

  • Step 7: Iteration

    When the maximum number of iterations is reached, the process is terminated; otherwise, circulate from the selection process.

5. NUMERICAL EXPERIMENT

Numerical experiments are conducted to assess the performance of the proposed chance-constrained model and hybrid algorithm. Particle swarm optimization (PSO) algorithm provides flexible, high performance mathematical programming solvers for linear programming, mixed integer programming, quadratic programming, and quadratically constrained programming problems. Since the problem in the literature [54] is similar to the problem in this paper, we can use PSO-M in the literature [54] to solve the model. Low [54] applied the “job-to-position” represent the particles and embedded a restarting strategy and three stopping criteria. The experimental results reveal that the performances of the PSO-M is quite satisfactory on both solution accuracy and efficiency. GA, GA-M and PSO-M [54] are used to solve three instances, respectively. GA denotes that initial solutions are randomly generated and without using Property 1.

Run GA, GA-M and PSO-M five times in each instance, respectively. All numerical experiments are performed on a computer with a i7 processor with a speed of 4.0 GHz and 16GB RAM. “No” column lists running index of algorithm. “GA” column lists objective function values obtained by the GA. “GA-M” column lists objective function values obtained by the heuristic method in Section 4. “PSO-M” column lists objective function values obtained by the modified PSO. “time” column lists the CPU time.

Assume that the number of job is 10. Processing time of job i is considered a normal uncertain variable: ξiN(i,1) for i=1,2,,10. Maintenance time is 1. Length of each availability interval is 12. Confidence levels α=0.8. Population size of GA is 50. In GA, crossover rate is 0.75. Mutation rate is 0.25. Maximum iteration number is 300. In PSO-M, the learning factors are set as c1=c2=2.0, inertia weight wmax=0.9, wmin=0.4 and Vmax=4.0. The rand1 and rand2 are random variables between 0 and 1. Maximum iteration number is 300.

Assume that the number of job is 20. Processing time of job i is considered a normal uncertain variable: ξiN(i,1) for i=1,2,,20. Maintenance time is 5. Length of each availability interval is 25. Confidence levels α=0.8. Population size of GA is 50. In GA, crossover rate is 0.8. Mutation rate is 0.2. Maximum iteration number is 200. In PSO-M, the learning factors are set as c1=c2=2.0, inertia weight wmax=0.9, wmin=0.4 and Vmax=4.0. The rand1 and rand2 are random variables between 0 and 1. Maximum iteration number is 200.

Assume that the number of job is 50. Processing time of job i is considered a normal uncertain variable: ξiN(i,1) for i=1,2,,50. Maintenance time is 10. Length of each availability interval is 55. Confidence levels α=0.8. Population size of GA is 50. In GA, crossover rate is 0.7. Mutation rate is 0.3. Maximum iteration number is 200. In PSO-M, the learning factors are set as c1=c2=2.0, inertia weight wmax=0.9, wmin=0.4 and Vmax=4.0. The rand1 and rand2 are random variables between 0 and 1. Maximum iteration number is 200.

In addition, we give an example about the operation process of Algorithm 1. If the measure is less than α, the job arrangement cannot be adopted.

The schedule result obtained by the LPT rule is

(10,9,8,7,6,5,4,3,2,1)(sequence of jobs)
for small scale (10 jobs). T=12 and t=1. Algorithm 1 is the key to obtain the result. Detailed procedure is as follows.
{ξ10T}=Φ(T)0.95>α=0.8
and
{ξ10+ξ9T}=Φ(T)0<α
where T=12. Subsequently, job 10 will be arranged to the first availability interval.

Since

{ξ9+ξ8T}=Φ(T)0.002<α,
job 9 will be arranged to the second availability interval.

Likewise,

{ξ8+ξ7T}=Φ(T)0.06<α,
job 8 will be arranged to the third availability interval.

The job 7 will be arranged to the forth availability interval by

{ξ7+ξ6T}=Φ(T)0.29<α.

The job 6 will be arranged to the fifth availability interval by

{ξ6+ξ5T}=Φ(T)0.71<α.

The jobs 5 and 4 will be arranged to the sixth availability interval by

{ξ5+ξ4T}=Φ(T)0.95>α,
and
{ξ5+ξ4+ξ3T}=Φ(T)=0.5<α.

The jobs 3, 2 and 1 will be arranged to the seventh availability interval by

{ξ3+ξ2T}=Φ(T)0.999>α,
and
{ξ3+ξ2+ξ1T}=Φ(T)0.97>α.

According to the above discussion, it yields M=7 and SumM=ξ3+ξ2+ξ1. And according to the Definition 3, it yields ξ3+ξ2+ξ1N(6,3). Then according to Example 2, it yields ΦSumM1(α)=6+33πln0.810.88.3. It implies that the total processing time of jobs in the Mth availability interval is 8.3 at the confidence level 0.8. According to Eq. (5), it yields Ψf1(α)=(71)(12+1)+8.3=86.3 and it implies that the makespan is 86.3 under confidence level 0.8.

The schedule result obtained by the LSPT rule is

(10,9,1,8,2,7,3,6,4,5)(sequence of jobs).
{ξ10T}=Φ(T)0.95>α=0.8,
{ξ10+ξ9T}=Φ(T)0<α,
{ξ10+ξ1T}=Φ(T)0.71<α,
and job 10 will be arranged to the first availability interval.

Since

{ξ9+ξ8T}=Φ(T)0.002<α,
{ξ9+ξ1T}=Φ(T)0.86>α,
{ξ9+ξ1+ξ2T}=Φ(T)=0.5<α,
jobs 9 and 1 will be arranged to the second availability interval.

Likewise, jobs 8 and 2 will be arranged to the third availability interval by

{ξ8+ξ7T}=Φ(T)0.06<α,
{ξ8+ξ2T}=Φ(T)0.86>α,
{ξ8+ξ2+ξ3T}=Φ(T)0.35<α.

The jobs 7 and 3 will be arranged to the forth availability interval by

{ξ7+ξ6T}=Φ(T)0.29<α,
{ξ7+ξ3T}=Φ(T)0.86>α.

The jobs 6 and 4 will be arranged to the fifth availability interval by

{ξ6+ξ5T}=Φ(T)0.71<α,
{ξ6+ξ4T}=Φ(T)0.86>α.

At last, job 5 will be arranged to the fifth availability interval.

According to the above discussion, it yields M=6 and SumM=ξ5. Since ξ5N(5,1), and according to Example 2, it yields ΦSumM1(α)=5+3πln0.810.85.76. It reveals that the total processing time of jobs in the Mth availability interval is 5.76 at the confidence level 0.8. According to Eq. (5), it yields Ψf1(α)=(61)(12+1)+5.76=70.76 and it reveals that the makespan is 70.76 under confidence level 0.8.

Tables 1 and 2 indicate that three algorithms can solve the model effectively. Table 3 indicates that the time required for GA-M are significantly less than the other two algorithms at large scale. The results obtained by GA-M are better than the other two algorithms. It reveals that LSPT and Property 1 play significant roles in the efficiency of the algorithm. In addition, the example of Algorithm 1 reveals that the LSPT outperforms LPT in the case of small scale obviously. The result suggests that LSPT can effectively reduce the amount of occupied availability interval.

No GA Time (s) GA-M Time (s) PSO-M Time (s)
1 71.9 15 67.5 15 71.6 13
2 72.7 13 66.1 17 70.1 15
3 71.5 12 67.8 15 70.4 19
4 70.7 15 70.3 19 72.7 12
5 69.4 10 68.9 13 71.0 17

GA, genetic algorithm; GA-M, improved genetic algorithm; PSO, particle swarm optimization.

Table 1

Results for 10 jobs.

No GA Time (s) GA-M Time (s) PSO-M Time (s)
1 253.5 20 245.3 26 251.3 23
2 251.7 22 247.5 25 253.2 25
3 258.8 26 245.5 25 251.7 25
4 253.3 26 247.1 24 255.9 26
5 254.5 28 243.4 25 258.3 26

GA, genetic algorithm; GA-M, improved genetic algorithm; PSO, particle swarm optimization.

Table 2

Results for 20 jobs.

No GA Time (s) GA-M Time (s) PSO-M Time (s)
1 1389.3 73 1330.2 68 1387.3 75
2 1385.5 79 1328.7 69 1389.8 74
3 1397.1 72 1330.6 69 1386.2 73
4 1392.2 69 1328.9 65 1397.4 75
5 1389.1 73 1325.1 68 1380.1 75

GA, genetic algorithm; GA-M, improved genetic algorithm; PSO, particle swarm optimization.

Table 3

Results for 50 jobs.

6. CONCLUSIONS

In this paper, a single machine scheduling problem with periodic maintenance was studied. To achieve the more accurate right decision in the turbulent and complex modern society, the uncertain factors were considered in the study. The processing time was considered an uncertain variable due to numerous practical historical data are unavailable or untrustworthy. To study the effects of uncertain variables on the scheduling problem, an uncertain chance-constrained model was proposed. In the model, pessimistic value was adopted to solve the imprecise objective function, and the chance-constrained programming method was adopted to regulate the confidence level of imprecise constraint satisfaction. Based on the uncertainty theory, the equivalent form of the chance-constrained model was obtained. Besides, a key algorithm for solving the model was also proposed. An efficient rule called LSPT combining the advantages of both LPT and SPT was proposed. To solve this model effectively, an algorithm GA-M combining the LSPT rule and Property 1 was proposed. Numerical experiments suggested that the proposed GA-M algorithm performs well.

For future work, it would be interesting to develop an improved method to obtain better solution for the problem. Future research will focus also on different shop environment (flow shop, job shop and open shop). In addition, other performance measures, for example total completion time, total weighted completion time and tardiness of jobs would also be considered.

CONFLICT OF INTERESTS

The authors declare they have no conflicts of interest.

AUTHORS' CONTRIBUTIONS

Jiayu Shen and Yuanguo Zhu contributed to the design and implementation of the research, to the analysis of the results, and to the writing of the manuscript.

ACKNOWLEDGMENTS

This work is supported by the National Natural Science Foundation of China (No.61673011) and Research Foundation of NIIT (YK18-10-02, YK18-10-03).

REFERENCES

16.Y. Zhu, Functions of uncertain variables and uncertain programming, J. Uncertain Syst., Vol. 6, 2012, pp. 278-288. http://www.worldacademicunion.com/journal/jus/jusVol06No4paper07.pdf
28.K. Yao, Multi-dimensional uncertain calculus with Liu process, J. Uncertain Syst., Vol. 8, 2014, pp. 244-254. http://www.worldacademicunion.com/journal/jus/jusVol08No4paper02.pdf
35.B. Liu, Some research problems in uncertainty theory, J. Uncertain Syst., Vol. 3, 2009, pp. 3-10. http://www.worldacademicunion.com/journal/jus/jusVol03No1paper01.pdf
Journal
International Journal of Computational Intelligence Systems
Volume-Issue
13 - 1
Pages
193 - 200
Publication Date
2020/02/23
ISSN (Online)
1875-6883
ISSN (Print)
1875-6891
DOI
10.2991/ijcis.d.200214.003How to use a DOI?
Copyright
© 2020 The Authors. Published by Atlantis Press SARL.
Open Access
This is an open access article distributed under the CC BY-NC 4.0 license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - JOUR
AU  - Jiayu Shen
AU  - Yuanguo Zhu
PY  - 2020
DA  - 2020/02/23
TI  - A Single Machine Scheduling with Periodic Maintenance and Uncertain Processing Time
JO  - International Journal of Computational Intelligence Systems
SP  - 193
EP  - 200
VL  - 13
IS  - 1
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.d.200214.003
DO  - 10.2991/ijcis.d.200214.003
ID  - Shen2020
ER  -