A joint model of production scheduling and predictive

ORIGINAL ARTICLE

A joint model of production scheduling and predictive maintenance for minimizing job tardiness

Ershun Pan &Wenzhu Liao &Lifeng Xi

Received:15July 2010/Accepted:15September 2011/Published online:4October 2011#Springer-Verlag London Limited 2011

Abstract As increasingly diverse tasks are being processed on single multi-functional machine,production scheduling has become a critical issue in the planning and management of manufacturing processes.However,the majority of produc-tion scheduling literature ignores machine availability and assumes that machine is available all the time.In reality,machines physically deteriorate with increased usage and time.Thus,there is an intense need for manufacturing industries to reduce unexpected breakdowns and remain competitive,and motivating maintenance operations should be integrated into production scheduling models.With the advancements in sensor and prognostic technologies,machine ’s condition can be monitored and assessed over time through conducting predictive maintenance.Hence,based on this scheme,this study proposes a single-machine-based scheduling model incorporating production scheduling and predictive maintenance.A machine ’s effective age and remaining maintenance life are introduced to describe machine degradation.Finally,a numerical example is given;the computational results show that this integrated schedul-ing model has better performance than those existing models,which proves its efficiency.

Keywords Production scheduling .Predictive

maintenance .Health index (HI).Effective age .Remaining maintenance life (RML).Tardiness

1Introduction

In today ’s competitive market,different kinds of single machine have been designed to be able to process various products (e.g.,intelligent machine tool)and conduct diverse tasks.Hence,how to effectively arrange the sequence of tasks for a given single machine,that is production scheduling,has become a critical issue in the planning and management of manufacturing processes.As an important component of manufacturing industry,production scheduling has been widely studied and various determin-istic optimization models have been developed to maximize some measures of customer satisfaction [1].In manufactur-ing industry,production scheduling can have a major impact on the productivity of a process,it can minimize the production time and the cost by determining what to make and when to make for a production facility [2].Overall,production scheduling aims to maximize the efficiency of a given operation and ultimately reduce costs.Since the 1950s,many production scheduling models for single-machine problem,flow and job shop problem,and capacitated lot-sizing problem have been developed [3–6].And single-machine problem has been most studied among all the scheduling problems.The best research existing for a vast set of problem specifications are the procedures for minimizing the mean flow time,the maximum tardiness,and the number of late tasks.All of these procedures seek to determine the optimal task sequence based on different objectives.Based on the single-machine prob-lem,other kinds of problems such as parallel machines problem or flow shop problems are studied (discussed in Refs.[7–9]).

Although the previous theoretical production scheduling models studied how to make a good task schedule,they usually do not take machine availability constraints into

E.Pan (*):L.Xi

Department of Industrial Engineering and Logistics Management,Shanghai Jiao Tong University,

Shanghai 200240,People ’s Republic of China e-mail:pes@cee02d639b6648d7c1c74632

W.Liao

Department of Industrial Engineering,Chongqing University,Chongqing 400030,People ’s Republic of China

Int J Adv Manuf Technol (2012)60:1049–1061DOI 10.1007/s00170-011-3652-4

account and assume machines are always available for processing the tasks during the planning time horizon,yet this assumption is inappropriate in many real-world scheduling cases[5,10].In reality,machine breakdown is common after long-time operation,hence,the machine will be unavailable while processing tasks due to its failures [11].Since machine breakdown will reduce production efficiency,maintenance as an important part in manufac-turing systems is used to keep machines in good condition to decrease failures,which makes maintenance planning become more and more important in manufacturing processes.Hence,maintenance should be considered as a part of production scheduling models so that the availability of a machine is known as opposed to assumed,resulting in more robust production schedules.Like machine break-downs,when performing maintenance operations,the tasks being processed must be stopped.The machine will be unavailable when an accidental breakdown or a mainte-nance operation occurs.Thus,a good maintenance planning should be considered to make production scheduling model more realistic.As machine breakdown is stochastic and maintenance is deterministic,maintenance planning can be treated as availability constraint in a production scheduling model.

As production scheduling models with the consideration of maintenance operations arouse great interest of research-ers,the machine availability problem for production scheduling models has been widely discussed in the past decades.However,those production scheduling models with maintenance planning usually do not consider machine degradation.Most of them just pre-design a fixed mainte-nance interval and arrange job sequences based on this maintenance interval,which cannot show maintenance operation’s real influence on production scheduling model. The related literature review is given below in Section2. Hence,in order to describe the interaction between production scheduling and maintenance planning,this study is devoted to propose an integrated scheduling model by incorporating production scheduling and predictive main-tenance planning simultaneously,with the aim of minimiz-ing the maximum tardiness.The single-machine problem is selected to be a fundamental research.A machine’s effective age and remaining maintenance life are introduced to describe machine’s deterioration process.

The remainder of this paper is organized as follows. Section2shows the literature review about previous research.Section3introduces the development of this integrated production scheduling model.And problem description and notation are given in Section4.Then, Section5presents the integrated production scheduling model considering predictive maintenance planning subject to machine degradation.Section6gives a numerical example,and discussions are provided to compare the result obtained by this proposed scheduling model with those obtained by some previous production scheduling models.Finally,the conclusion and future research are in Section7.

2Literature review

Scheduling is one of the most widely researched areas of operational research,which is largely due to the rich variety of different problem types within the field.And the types of scheduling problems with maintenance operations that arise in production industries are focused in this paper.

In the past decades,as maintenance planning for the manufacturing processes becomes more and more impor-tant,some research has been done to consider the machine availability problem with maintenance as an availability constraint and study production scheduling models with maintenance operations based on different customer requirements(i.e.,objectives)[12,13].Adiri et al.studied a production scheduling model with maintenance opera-tions for a single machine.In their paper,machine breakdown is assumed and the number of tardy jobs is minimized[1].Lee and Liman considered a two-parallel-machine scheduling problem with the aim to minimize the total completion time.In this scheduling model,one machine which has the availability constraint is discussed [14].Then,Mosheiov studied the same problem.In his scheduling model,he assumed each machine was unavail-able in an interval[15].Later,Espinouse et al.worked on a flow shop scheduling problem.They assumed a limited machine availability in their scheduling model to arrange maintenance operations with the aim of minimizing the makespan[8].In these researches,some basic concepts are given to study scheduling models with maintenance operations.However,most of them assumed there was only one interval in which machine was unavailable.It seems unpractical.Based on this scheme,researchers began to consider several maintenance intervals.For example,Qi et al.studied a scheduling problem with periodic mainte-nance planning.In their model,they assumed several intervals in which machine was unavailable and took them to be decision variables in order to minimize the total completion time[16].

Although these previous research have shown their performance to solve production scheduling problem,most of them considered periodic maintenance which had fixed maintenance interval.As periodic maintenance pre-determines a fixed time interval to perform maintenance operations(i.e.,characteristics of the unavailability periods is known in advance),machine idleness will appear due to the incoordination of the total processing time of prior batch and the fixed time interval.Hence,though these

1050Int J Adv Manuf Technol(2012)60:1049–1061

research have considered periodic maintenance planning into production scheduling model,it seems not economic due to machine idleness[17–19].If maintenance operations could be well planned according to jobs’processing time and machine’s condition,much more resources will be saved.Thus,machine’s condition should be known ahead to help arrange flexible maintenance intervals for appropri-ate maintenance operations.Based on this scheme,preven-tive maintenance is studied for the optimization of those cases in which maintenance operation is controllable[20–23].Although there is some research considering preven-tive maintenance during production processes nowadays, most of them involved the use of common function distributions to describe machine degradation,which seems unpractical[24,25].Therefore,it becomes essential to develop good maintenance planning based on machine’s real deterioration process.

Nowadays,in Prognostics and Health Management research,with the advancements in sensor and intelligent prognostic technologies,machine’s condition can be mon-itored and machine degradation can be estimated[26–28]. For example,Yang et al.proposed a new method for scheduling of maintenance operations in a manufacturing system using continuous assessment and prediction of the level of performance degradation of manufacturing equip-ment[29].The continuous assessment and prediction of a machine’s performance can thus enable collaborative machine life cycle management,which could help predict machine’s residual life[30–33].And with the information of machine’s residual life,predictive maintenance can be conducted to prevent unexpected machine breakdowns and unscheduled costly downtime.As identification of machine’s residual life could help arrange maintenance operations in advance to keep machines in good operation condition,it becomes important to integrate predictive maintenance planning into production scheduling[34].Thus,in order to develop good production scheduling model with the consideration of machine’s real deterioration process,an integrated production scheduling model is proposed in this study to solve a single-machine problem by integrating production scheduling and predictive maintenance simul-taneously.More specifically,minimizing the maximum tardiness of jobs is considered as the objective,which can help maximize customer satisfaction(e.g.,shorten deliv-ery time or lead time).

3Development of the integrated production scheduling model

Compare with those previous production scheduling mod-els with maintenance planning,this study develops an integrated scheduling model with production scheduling and predictive maintenance planning focusing on the following parts.

cee02d639b6648d7c1c74632ually,maintenance models are typically stochastic

models accompanied by optimization techniques designed to maximize the machine availability or minimize the total cost[35].Although there are some papers published showing the great use of predictive maintenance planning in industry,few of them are involved in a production scheduling problem.Thus,in order to arrange appropriate maintenance operations based on machine degradation during the planning horizon,this study considers predictive maintenance planning into production scheduling.Moreover,for a machine,as maintenance operation occupies the pro-cessing time,and no jobs can be processed at that time, frequent maintenance operations will delay production process.However,if maintenance operation is delayed to keep the production,machine’s reliability decreases.

Hence,this study explicitly integrates production scheduling and predictive maintenance planning simul-taneously into an integrated scheduling model but not only considers them individually.

2.In reality,machines suffer increasing wear with

increased age and usage due to degradation,which causes low reliability.Most previous scheduling mod-els with maintenance planning usually do not consider machine’s real deterioration process and just pre-design

a fixed time interval and then arrange the jo

b sequences

based on this maintenance interval.It is obvious that this kind of inflexible maintenance interval will ignore machine reliability;moreover,machine idleness may occur.In order to meet more practical situations,this paper studies machine’s deterioration process,and maintenance operations to restore the machine can be appropriately performed.Thus,in this study,a concept of machine’s remaining maintenance life(RML)is proposed to describe machine degradation.By judging RML,maintenance operations are performed.With the controllable maintenance interval which is solved by the stochastic production scheduling model(either mathematical or simulated),the job sequence can be well arranged to avoid machine idleness so as to make full use of machine.In addition,this scheduling model will schedule multiple maintenance operations,but not schedule only one maintenance operation during the whole planning horizon[17,36].

cee02d639b6648d7c1c74632ually,machine’s actual age increases with time,

however,it cannot describe machine’s real health status exactly.Thus,a concept of effective age is proposed in this study to describe machine’s real health status which has a corresponding relationship with health index(HI).

Considering that the frequency of maintenance oper-

Int J Adv Manuf Technol(2012)60:1049–10611051

ations will influence machine degradation(i.e.,after frequent maintenance operations,the machine will dete-riorate quickly),a machine cannot shift back to an exactly new status after predictive maintenance operation in reality,this study also introduces an improvement factor of machine’s recovery to adjust machine’s effective age and describe the effect of maintenance operations before and after maintenance,which makes maintenance oper-ations meet more practical situations[37].

With these aforementioned considerations,this study tries to develop an integrated production scheduling model by incorporating production scheduling and predictive maintenance planning to enhance production scheduling research and bridge the gaps between theory and reality. 4Problem description

Notations

n Number of jobs to be processed at time zero

p i Processing time of job i,i∈{1,2,…,n}

d i Du

e date o

f job i

C i Completion time of job i

L i Lateness of job i

T i Tardiness of job i

p[i]Processing time of the i th job in the sequence

C[i]Completion time of the i th job in the sequence

L[i]Lateness of the i th job in the sequence

T[i]Tardiness of the i th job in the sequence

H0Machine’s health index at time zero,H0∈[0,1.0](1 means new status)

H t Machine’s health index at time t,H t∈[0,1.0]

H safe Machine’s health index at safety threshold

H fail Machine’s health index at breakdown threshold

υi Machine’s effective age before predictive

maintenance operation

ωi Machine’s effective age after predictive

maintenance operation

b i Influence factor of the frequency of maintenance

operations,b i>1

c Maintenance adjustment factor,0

ηi Improvement factor of machine’s recovery

t m Time for performing predictive maintenance operation

t r Time for replacement

M[l]Ordinal of maintenance periods in the sequence,l∈N T max Maximum tardiness

T total Total tardiness

A Job sequence

This paper studies a single-machine scheduling problem in which the machine is not continuously available due to machine degradation,hence,predictive maintenance oper-ations are performed based on machine’s condition.In this paper,a machine’s HI is introduced to represent the machine’s health status[38].After each maintenance operation,the machine will be recovered to be“as good as new.”The initial HI of the machine is H0,when the machine’s health status degrades to H fail level,it will break down,thus requiring repair work/maintenance.The time period from H0to H fail is called remaining useful life(RUL;

i.e.,RUL?t H

fail

àt H

).As the machine’s breakdown will result in process interruption and huge losses,a safety threshold of H safe is set before the degradation reaches H fail which will trigger a predictive maintenance operation, preventing the breakdown before maintenance can be conducted.The time period from H0to H safe is denoted as RML and RML?t H

safe

àt H

.Thus,predictive maintenance operations are performed based on the RML,subject to machine’s deterioration process during the planning time horizon(seen in Fig.1).And the time between H safe and H fail can be used as a buffer to help address unexpected situations as well as to allow for slight adjustments when the predicted result varies.

Then,this predictive maintenance information is integrated into production scheduling model.As in Fig.2a,there are a set of n jobs required to be processed on a single machine,and all of the jobs are ready to be released at time zero.While processing,only one job can be processed at one time on the machine.Suppose that one job preempts another is not permitted(i.e.the job is nonresumable and it cannot be interrupted after starting its service on the machine).The similar assumption can be found in the published papers by Merten and Muller[39] and Schrage[40].Predictive maintenance operations can reduce the increasing risk of machine failures and restore the machine to be“as good as new”(i.e.the machine is renewed and its HI returns to nearly one considering the improvement factor mentioned in Section3).Based on the RML information shown in Fig.1,a job sequence integrated with predictive maintenance planning is obtained(seen in Fig.2b).In this study,the optimal production scheduling integrating predictive maintenance

H

H

H

Fig.1A machine’s deterioration process

1052Int J Adv Manuf Technol(2012)60:1049–1061

planning is determined by minimizing the maximum tardiness.

5Formulation of the integrated production scheduling model

The problem to be addressed and the objective to be achieved have been introduced above.This section will demonstrate the development of an integrated produc-tion scheduling model to solve this problem,and the mathematical framework for the integrated production scheduling model is established to prove the structural characteristics of the optimum schedule subject to following assumptions.

Assumptions:

1.A single machine is studied;

2.The machine is subject to a deterioration process;

3.The machine begins a new degradation process after

predictive maintenance operations;

4.The machine can only process one job at one time;

5.The setup time for each job is ignored;

6.Each job is nonresumable(i.e.,it cannot be interrupted

after it starts its service on the machine).

As mentioned above,with the advancements in sensor and intelligent prognostic technologies,machine degradation can be estimated and machine’s RML is obtained.In this model,the time period between each two adjacent maintenance operations is called one maintenance cycle.At the beginning of one cycle,the remaining time for conducting next maintenance will be determined first by the RML information.Then with the obtained RML information,the optimal planning for both jobs and maintenance operations will be generated subject to the pre-determined objective.While process-ing jobs,machine’s condition will be kept monitored during the planning horizon.At the end of this maintenance cycle,machine will be maintained to a good status.After that,a new cycle will be launched. Then,next RML is predicted for rescheduling the rest jobs.The same procedure will be applied to all cycles till there is no job left to be arranged.

Let the effect of predictive maintenance operations on machine’s recovery can be described by an improvement factorηi that is defined as

h i?cát r

eTb iáie1TThen,machine’s effective age can be given by

w i?1àh i

eTáu ie2TBased on Eq.2,machine’s effective age for each predictive maintenance cycle can be deduced as

u1?RML1?T H

safe

àT H

e3Tw1?1àh1

eTáu1?1àh1

eTáRML1

?1àh1

eTáT H

safe

àT H

eTe4T

u2?w1tRML2

?1àh1

eTáRML1tRML2

e5Tw2?1àh2

eTáu2

?1àh2

eTáw1tRML2

eT

?1àh2

eTá1àh1

eTáu1tRML2

?

?1àh2

eTá1àh1

eTáRML1tRML2

?

?1àh2

eTá1àh1

eTáRML1t1àh2

eTáRML2

e6T

......

......

u N?

Y

Nà1

i?1

1àh i

eTáRML1tááát

Y

Nà1

i?nà1

1àh i

eTáRML Nà1tRML N?

X

Nà1

j?1

Y

Nà1

i?j

1àh i

eTáRML j

"#

tRML N

e7Tw N?

Y N

i?1

1àh i

eTáRML1t

Y N

i?2

1àh i

eTáRML2tááátY N

i?N

1àh i

eTáRML N?

X N

j?1

Y N

i?j

1àh i

eTáRML j

"#

e8TNote that

P n

j?1

p j

P N

l?1

RML l.

Fig.2Illustration of production scheduling with maintenance

planning

Int J Adv Manuf Technol(2012)60:1049–10611053

With the aim of minimizing the maximum tardiness,it is thus essential to obtain the completion time of each job first so as to compute its corresponding tardy time.Then,the maximum tardiness among all the jobs is obtained and ready to be minimized.In this scheduling model,a set of jobs to be processed,including J 1,J 2,…,and J n ,respectively.And there are several maintenance periods,M [1],M [2],…,and M [l ](i.e.no less than one maintenance period).As C i denotes the completion time of job i ,the lateness of job i should be L i ?C i àd for i ?1;2;:::;n

e9T

If one job is processed ahead of its due date,it has no

tardy time.That means L i <0makes T i =0.Thus,the tardiness of job i can be inferred as T i ?max 0;L i f g

e10T

Hence,with the aim of minimizing the maximum tardiness of all the jobs,the corresponding T max =max {0,T i }must be minimized.Suppose x i,j as one decision variable and let

x i ;j ?

1;if the i th job performed is job j

0;otherwise (

for i ?1;2;:::;n ;j ?1;2;:::;n

e11TWith the decision variable x i,j ,the processing time for

the ith job in the sequence can be deduced as p ?i ?

X n j ?1

p j áx i ;j

àá

e12T

Considering the development of this integrated schedul-ing model discussed in Section 3,the completion time for each job as a random variable should be influenced by 1.The completion time of the previous jobs;2.The processing time of the current job;3.Machine ’s current health status;4.Machine ’s deterioration process;and

5.

Time for performing predictive maintenance operation.

Thus,considering these influences,for the first job in the sequence,the expected value of its completion time C [1]can be constructed as E C 1? àá

?p 1? tt m áN 1? e13T

s :t :p ?1 ?

X n j ?1

p j áx 1;j

àá

e14T

p ?1 RML 1

e15T

N ?1 ?

p ?1 t H saf e

"#

t

p 1? àt

H safe áp 1? t H safe j k t H safe àt H 0

66647775e16T

which includes two parts:the processing time of the first job in the sequence and the probable time for performing predictive maintenance operations before processing the

first job.In Eq.14,P

n j ?1

p j áx 1;j àádenotes the processing time

of J [1].And Eq.16denotes the probable number to perform

predictive maintenance operations before processing J [1].Because predictive maintenance operation is assumed to restore the machine to be “as good as new ”,if one predictive maintenance operation is performed,the machine is renewed and the next time interval to perform predictive maintenance operation is estimated by machine ’s RML based on the safety threshold.

With the expected value C [1]obtained by Eq.13,the expected value of the lateness is inferred as E L 1? àá?E C 1? àáàd j e17THence,considering Eq.10,the expected value of the tardiness of J [1]should be E T ?1 àá?max 0;E L ?1 àáèée18TIn this production scheduling model,suppose Q i (i ∈{1,2,…,n })to be a set of jobs having been selected (e.g.if job J [1]has been selected to be processed,there is Q 1={J [1]}before processing the second job in the sequence).Hence,the expected value of the completion time for the second job in the sequence C [2]can be given by E eC ?2 T?p ?2 tt m áN ?2 tE eC ?1 T

e19T

s :t :p ?2 ?X

j 2I

ep j áx 2;j Te20T

p ?2 max RML 1àp ?1 àá;RML 2

àá

e21T

N 2?

?p 2? t H safe

"#tp 2? àt

H safe áp 2? t H safe j k t H safe àt H t

E C ?1 eT

666664777775for I ?1;2;:::;n f g \Q 1

e22T

1054Int J Adv Manuf Technol (2012)60:1049–1061

Thus,the expected value of the lateness of J [2]is E L 2? àá?E C 2? àá

àd j

e23T

The expected value of the tardiness of J [2]should be E T 2? àá?max 0;E L 2?

àáèé

e24TThen,according to the expected value of the completion

time of J [1]and J [2]obtained in Eqs.13and 19,it can be deduced that the expected value of the completion time C [i ]of J [i ]is

E eC ?i T?p ?i tt m áN ?i tE eC ?i à1 T

e25T

s :t :p ?i ?

X

j 2I

ep j áx i ;j Te26Tp ?i max RML i àp ?i à1 àá;RML i

àá

e27T

N i ? ?p i ? t H safe

"#tp i ? àt

H safe áp i ? t H safe j k t H safe àt H t

E C ?i à1 eT 666664777775e28T

X

j 2I x i ;j ?1;I ?1;2;:::;n f g \Q i à1

e29T

X n i ?1

x i ;j ?1;j ?1;2;:::;n e30T

x i ;j binary ;i ?1;2;:::;n ;j 21;2;:::;n f g \Q i à1

e31T

Fig.3The brief flowchart of acquiring the optimal job sequence with predictive maintenance operations

Table 1The original data for example from Liao and Chen [17](in hours)

Number of jobs Job1Job2Job3Job4Job5Job6Job7Job8Job9p i 153522344d i

1

13

2

30

10

13

20

12

14

First

cycle

Second cycle Third cycle Fourth cycle

Fig.4The obtained schedule based on predictive maintenance

planning

Int J Adv Manuf Technol (2012)60:1049–10611055

where p [i ]in Eq.26represents the processing time of J [i ]and N [i ]in Eq.28represents the probable number to perform predictive maintenance operations before process-ing J [i ]in this maintenance cycle.Then,the expected value of the lateness of J [i ]should be E eL ?i T?E eC ?i Tàd j

e32T

Hence,the expected value of the tardiness of J [i ]is obtained as

E eT ?i T?max 0;E eL ?i T

èé

e33TTherefore,with the aim of minimizing the maximum

tardiness in this integrated production scheduling model,the resulting mathematical programming formulation can be given by minimize T max ?max E T i ? àáèé

e34Ts :t :

X n i ?1

x i ;j ?1;j ?1;2;:::;n

e35T

X n j ?1

x i ;j ?1;i ?1;2;:::;n

e36T

x i ;j binary ;i ?1;2;:::;n ;j ?1;2;:::;n e37T

In addition,in optimization research,since there may be many optimal solutions in terms of one optimization criterion,a second optimization objective is usually used to filter the best one out of them.In other words,as the maximum tardiness of several job sequences obtained by the proposed scheduling model may have the same results,an additional criterion is selected to search the optimal job sequence among them.For this mathemat-ical model,a second priority optimization objective of minimizing the total tardiness of all the tardy jobs is thus adopted to measure the performances of job sequences that have the same maximum tardiness (i.e.,

if two job sequences have the same maximum tardiness,

then the job sequence that has smaller total tardiness of all the tardy jobs is selected to be the optimal one).

That is to minimize T total ?

P

E T i eT.Based on the description of mathematical formulation for the integrated production scheduling model,a brief flowchart of acquir-ing the optimal job sequence with predictive maintenance operations is given in Fig.3.With the equations established above,the maximum tardiness and total tardiness of all the tardy jobs can be obtained to decide the optimal solution.

6Case study

This study tries to propose an integrated production scheduling model with predictive maintenance planning and make it applicable for complicated situations with machine availability considered.In Section 6.1,a numerical example will be given to demonstrate the proposed integrated scheduling model.Section 6.2will present the comparison obtained by this proposed scheduling model and three previous models as follows:

1.Production scheduling model without maintenance

planning;2.Production scheduling model with periodic mainte-nance planning;and

3.Individual production scheduling and predictive main-tenance planning.6.1A numerical example

In this paper,a single-machine scheduling problem intro-duced by Liao and Chen [17]with the aim of minimizing the maximum tardiness is studied.In this example,there are nine jobs required to be processed.The parameters of each job are indicated in Table 1,including job ’s processing time and job ’s due date.The time for performing maintenance operation is set to be t m =2and the time for replacement is t r =10.And the influence factor of the frequency of

Table 2The RML values estimated at the beginning RML 1RML 2RML 3RML 4RML 5RML 67.05

11.29

9.44

7.68

6.13

4.86

Table 3The RML values estimated after 1st maintenance operation RML 1RML 2RML 3RML 4RML 5RML 611.03

9.89

8.26

6.72

5.38

4.26

Table 4The RML values estimated after 2nd maintenance operation RML 1RML 2RML 3RML 4RML 5RML 68.12

7.19

6.01

4.88

3.91

3.10

Table 5The RML values estimated after 3rd maintenance operation RML 1RML 2RML 3RML 4RML 5RML 66.30

5.66

4.73

3.85

3.08

2.44

1056

Int J Adv Manuf Technol (2012)60:1049–1061

maintenance operations is b i ?13i t4eT12i t4eT=.The maintenance adjustment factor is c =0.003.For this repair-able single machine,machine ’s initial HI is H 0=0.92,and its safety threshold is set to be H safe =0.31.Machine degradation follows the estimated function presented below,where the monitoring interval is 45s.H t ?0:252902áH t à1t0:218719áH t à2

t0:119930áH t à3t0:093162áH t à4t7:11?10à5

e38T

The job schedule considering each predictive maintenance decision with the overall optimal objective function value (i.e.,minimum maximum tardiness)can be identified as a global optimal solution.After each RML prediction cycle,a new optimal solution will be searched based on the rest jobs.First,compute machine ’s RML according to its initial HI and estimated function,and based on Eq.25,the expected value of completion time of these jobs can be calculated.The probable time for performing predictive maintenance oper-ations prior to the ith job can then be estimated by the current job sequence.Then,by computing the expected value of the lateness of J [i ]through Eq.32,its expected value of the tardiness can be obtained through Eq.33.Finally,with the objective function shown in Eq.34,the maximum tardiness for different job sequences is compared,and the optimal job sequence is selected with the minimum tardiness.The schedule solved by this integrated production scheduling model is presented in Fig.4.There are four predictive maintenance cycles.

1.For the first cycle,the estimated RML values are

presented in Table 2.

The schedule including the first predictive maintenance operation is

job1àjob3àjob5àM àjob8àjob6àjob2àjob9

àjob7àjob4It means that for the first planning horizon,after processing job1,job3,and job5,one predictive mainte-nance operation should be performed,the rest jobs (i.e.,job2,job4,job6,job7,job8,and job9)are ready for the next cycle.

2.For the second cycle,the estimated RML values are

presented in Table 3.Through the proposed production scheduling model,there are four schedules obtained with the same maximum tardiness,shown as below:

Schedule 1job 6àjob 8àjob 2àM àjob 9àjob 7àjob 4Schedule 2job 8àjob 6àjob 2àM àjob 9àjob 7àjob 4Schedule 3job 8àjob 2àjob 6àM àjob 9àjob 7àjob 4Schedule 4job 2àjob 8àjob 6àM àjob 9àjob 7àjob 4Then,after using the second criterion of minimizing the total tardiness mentioned in Section 5,schedule 2with T total =7is selected to be the optimal one:job8àjob6àjob2àM àjob9àjob7àjob4

It means for the second planning horizon,after process-ing job8,job6,and job2,one predictive maintenance operation should be performed,the rest jobs (i.e.,job4,job7,and job9)are ready for the next cycle.

3.For the third cycle,the estimated RML values are

presented in Table 4.

Table 6The optimal result of the obtained schedule based on the proposed model

Job sequence 1–3–5–M –8–6–2–M –9–7–M –4Job/maintenance 13

5

M

86

2

M

97

M

4Maintenance cycle 1234C i 1468

12141921

252830

35d i 1210121313142030T i 020

16

11

8

5

T total

33

Table 7The schedule obtained by traditional production sched-uling (no maintenance planning)

Job sequence Job1Job3Job5Job8Job6Job2Job9Job7Job4C i (no failure)146101217212429T i (no failure)020004740C i (with failure)14621.5923.5928.5942.6245.6261.74T i (with failure)

2

9.59

10.59

15.59

28.62

25.62

31.74

Int J Adv Manuf Technol (2012)60:1049–10611057

The schedule including the third predictive maintenance operation is

job9àjob7àM àjob4

Hence,for the third planning horizon,after processing job9and job7,one maintenance operation should be performed,the rest jobs (i.e.,job4)is ready for the next cycle.

4.For the third cycle,the estimated RML values are

presented in Table 5.As the rest jobs ’total processing time (i.e.,p 4=5)is less than RML 1shown in Table 5,no maintenance operation is performed.Thus,during the whole planning horizon,three predictive maintenance operations are planned.

Table 6indicates the optimal result of the obtained schedule.Each job ’s tardiness is presented.It can found that the maximum tardiness is 11of job9,and there are six jobs delayed.With the information of the obtained tardiness of these delayed jobs,manufacturers can communicate with customers to better plan the suitable due date and reach a win –win situation.

Moreover,this proposed production scheduling model can make dynamic scheduling so as to meet the requirements of rescheduling for urgent situations or continuously scheduling for long term planning (i.e.,new jobs can be added into the rest unfinished job sequence for scheduling decision).Hence,this proposed scheduling model can plan the optimal production sequence with maintenance operations according to machine ’s deterioration process and even be effective for the urgent or continuous jobs situation to show good dynamic performance.6.2Result discussion

As this study explicitly tries to integrate production scheduling and predictive maintenance into one optimized scheduling model,in order to show its better performance

than those of previous production scheduling models,three cases are discussed:

1.Production scheduling model without maintenance

planning;

2.Production scheduling model with periodic mainte-nance planning;and

3.Individual production scheduling and predictive main-tenance planning.6.2.1Case 1:production scheduling model without maintenance planning

In this section,the example is discussed by using traditional production scheduling model without mainte-nance planning.As machine availability constraint is not taken into account (i.e.,assume the machine is always available for processing jobs during the planning time horizon),there are no machine breakdowns and main-tenance time.Thus,the solution is obtained mainly based on job ’s processing time and their due date,without considering machine degradation.The job sequence is obtained as

job1àjob3àjob5àjob8àjob6àjob2àjob9àjob7àjob4

The third row of Table 7presents the tardiness of each job in this job sequence,the maximum tardiness is seven of job9without considering machine degradation.However,in reality,machine will degrade with increased usage and age.Thus,according to machine ’s initial HI and the estimated function of machine ’s HI,there will be at least one machine failure occurring because machine ’s HI reaches 0.Based on RML estimation,the times to failure for several cycles are:7.59,11.88,8.75,and 6.78,respectively.Then,considering the job sequence obtained above,three machine failures are supposed to occur after job5,job2,and job7.As the time for replacement is 10,seven tardy jobs will appear and the

Fig.5The schedule obtained by Liao and Chen [17]

Table 8Results of the schedule obtained by Liao and Chen [17]

Job sequence Job1Job5Job2M Job3Job8M Job6Job9M Job7Job4C i 13810

131720

222630

3338d i 1101321213142030T i 00

11

5

9

12

13

8

T total

58

1058

Int J Adv Manuf Technol (2012)60:1049–1061

maximum tardiness is 31.74(over 31:74à11eT=11%186%).Hence,it is obvious that this job sequence performs much worse than the one obtained by our proposed scheduling model.If much more jobs are required to be processed,the machine provided scheduled maintenance should be much more effective than the ones without maintenance planning.As maintenance is a much more comprehensive operation than repair,perhaps corresponding to the replacement of several key components of the machine,maintenance planning must be considered into production scheduling models.

6.2.2Case 2:production scheduling model with periodic maintenance planning

In previous production scheduling research with mainte-nance planning,most of them considered periodic mainte-nance planning.Hence,this section will discuss the example solved by production scheduling model consider-ing periodic maintenance.In Liao and Chen ’s paper,they assumed the fixed maintenance interval is 8,and the job sequence with periodic maintenance obtained by their model is shown in Fig.5.The schedule is arranged as job1àjob5àjob2àM àjob3àjob8àM àjob6àjob9

àM àjob7àjob4In Table 8,the result shows that the maximum tardiness is 13of job7and the total tardiness is cee02d639b6648d7c1c74632paring with the result in case 1,the added maintenance planning can reduce the tardiness and enhance the productivity,and avoid repair cost as well.However,there appears one issue.The rescheduled job sequence brings the idleness due to the fixed mainte-nance interval.It can be seen that there is idleness before performing the second and the third maintenance operations.And the total idleness reaches three,which makes machine availability low.

Sbihi and Varnier [18]studied the same problem by using their own proposed model.And the schedule obtained by their model is shown in Fig.6.The schedule is arranged as job1àjob3àjob8àM àjob5àjob2àM àjob6àjob9

àM àjob7àjob4Sbihi and Varnier ’s solution (Fig.6)indicates the idleness in their schedule appears at the same place in Liao and Chen ’s solution.The total idleness is also three.In Table 9,the result shows that the maximum tardiness is 13of job7and the total tardiness is 50.Although the maximum tardiness of two solutions are the same,the total tardiness obtained by Sbihi and Varnier is shorter.This shows a better performance of Sbihi and Varnier ’s model.However,comparing these two results with the result obtained by our proposed scheduling model in Section 6.1,it can be found that there is no idleness in the solution solved by our proposed model,moreover,the maximum tardiness (saving 13à11eT=11%18%)and the total tardiness (saving 50à33eT=33%52%)are shorter.Obvi-ously,our proposed scheduling model with controllable time interval for maintenance operations can make full use of machine availability and avoid machine idleness,which shows its good performance to support good scheduling (Table 6).

6.2.3Case 3:individual production scheduling and predictive maintenance planning

This section discusses the example solved by considering individual production scheduling and predictive mainte-nance planning.First,the job sequence is solved by production scheduling model.Then,predictive maintenance operations are planned.As shown in case 1,if machine availability constraint is not taken into account in produc-tion scheduling model,the obtained job sequence is job1àjob3àjob5àjob8àjob6àjob2àjob9àjob7àjob4.

Fig.6The schedule obtained by Sbihi and Varnier [18]

Table 9Results of the schedule obtained by Sbihi and Varnier [18]

Job sequence Job1Job3Job8M Job5Job2M Job6Job9M Job7Job4C i 14810

121720

222630

3338d i 1212101313142030T i 02

2

4

9

12

13

8

T total

50

Int J Adv Manuf Technol (2012)60:1049–10611059

Then,predictive maintenance planning should be sched-uled(i.e.,pre-determine the optimal time intervals for maintenance operations).Based on the RML values presented in Table2,the job sequence is rescheduled by adding maintenance operations,shown as

job1àjob3àjob5àMàjob8àjob6àjob2àMàjob9àjob7àMàjob4

In this schedule,as the total processing time of job1, job3,and job5is six,one maintenance operation should be performed before job8.Then,because the total processing time of job8,job6and job2is11,one maintenance operation should be performed before job9.For the third cycle,as the total processing time of job9and job7is seven, one maintenance operation should be performed before job4.Finally,because the processing time of job4is5< 7.68,no additional maintenance is planned.In this case,the total idleness cee02d639b6648d7c1c74632paring with the result obtained by our proposed scheduling model,the job sequence considering individual production scheduling and predic-tive maintenance planning has longer maximum tardiness (over12:34à11

eT=11%12%)and total tardiness(over 42:61à33

eT=33%29%),and even brings idleness(see Table10.Therefore,the integrated scheduling model with controllable time intervals for maintenance operations can show better performance and make full use of the machine availability,which can optimize real production processes.

7Conclusions and future work

As production scheduling is widely studied resulting in many deterministic optimization models being designed to maximize customer satisfactions,the importance of pro-duction scheduling has been gradually gaining recognition, by decision makers for the use in the planning and management of manufacturing processes.However,in reality,maintenance operations should be well integrated as a component of production scheduling due to the machine availability constraints.Based on this scheme,this study is devoted to proposing a single-machine-based integrated scheduling model incorporating both production scheduling and predictive maintenance planning with the objective of minimizing the maximum tardiness.In this integrated scheduling model,with the advancements in sensor and prognostic technologies,machine’s condition could be monitored and machine degradation could be estimated.Hence,the continuous assessment and prediction of machine’s performance can enable a collaborative machine life cycle management,which helps predict RML information throughout machine’s deterioration process.Through a case study,the computational results show that this integrated production scheduling model performs better than those previous production schedul-ing models.Therefore,this proposed scheduling model proves its efficiency on reducing tardiness as well as keeping machines in good operation condition,which can both maximize enterprise’s profit and customer’s satisfaction.In addition,this proposed scheduling model is even effective to meet the situations of requiring dynamic scheduling for urgent or continuously schedul-ing for long term planning.

In spite of many meaningful extensions that this proposed scheduling model has lend itself to,there is still further research needed.For example,although a safety threshold ahead of machine breakdown point is set to provide a buffer time that can be used for scheduling adjustment in case prediction is not accurate,that may be not enough,which requires further research to be conducted to make the prediction more accurate and reliable.We intend to explore these extensions as well as study multiple machines and/or flow shop problems in future research. Acknowledgments The authors would like to thank anonymous referees for their remarkable comments and great support by the National Natural Science Foundation of China(50875168and 71171130)and National High-Tech Research and Development Plan (2009AA043001).

References

1.Adiri I,Frostig E,Rinnooy KAHG(2006)Scheduling on a single

machine with a single breakdown to minimize stochastically the number of tardy jobs.Nav Res Logist38(2):261–271

2.Liu Y,Liu X,Zhao J(2008)Research on job-shop scheduling

optimization method with limited resources.Int J Adv Manuf Technol38(3–4):386–392

3.Graham RL,Lawler EL,Lenstra JK,Rinnooy AHG(1979)

Optimization and approximation in deterministic sequencing and scheduling:a survey.Ann Oper Res5:287–326

Table10The schedule obtained by considering individual production scheduling and predictive maintenance planning

Job sequence Job1Job3Job5M Job8Job6Job2M Job9Job7M Job4

C i1469.0513.0515.0520.0522.3426.3429.3433.7838.78 d i1210121313142030

T i020 1.05 2.057.0512.349.348.78 T total42.61

1060Int J Adv Manuf Technol(2012)60:1049–1061

4.Graves SC(1981)A review of production scheduling.Oper

Manag29(4):646–675

5.Pinedo ML(2008)Scheduling:theory,algorithms and systems.

Prentice-Hall,Englewood Cliffs

6.Dipak L,Uday KC(2009)A constructive heuristic for minimizing

makespan in no-wait flow shop scheduling.Int J Adv Manuf Technol41(1–2):97–109

7.Ho JC(1995)Flowshop sequencing with mean flowtime

objective.Eur J Oper Res81(3):571–578

8.Espinouse ML,Formanowicz P,Penz B(1999)Minimizing the

makespan in the two-machine no-wait flow-shop with limited machine cee02d639b6648d7c1c74632put Ind Eng32:497–500

9.Allouchea MA,Aounib B,Martelc JM,Loukila T,Reba?a A

(2009)Solving multi-criteria scheduling flow shop problem through compromise programming and satisfaction functions.

Eur J Oper Res192(16):460–467

10.Chen JS(2006)Optimization models for the machine scheduling

problem with a single flexible maintenance activity.Eng Optim38

(1):53–71

11.Liao W,Pan E,Xi L(2009)A condition-based maintenance

policy for intelligent monitored system.Int J Comput Appl Technol35:104–112

12.Arts RHPM,Knapp GM,Lawrence MJ(1998)Some aspects of

measuring maintenance in the process industry.J Qual Maint Eng 4:6–11

13.Schmidt G(2000)Scheduling with limited machine availability.

Eur J Oper Res121:1–15

14.Lee CY,Liman SD(1993)Capacitated two-parallel machine

scheduling to minimize sum of job completion time.Discret Appl Math41:211–222

15.Mosheiov G(1994)Minimizing the sum of job completion times

on capacitated parallel machines.Mathematical Computer Mod-eling20:91–99

16.Qi X,Chen T,Tu F(1999)Scheduling the maintenance on a

single machine.J Oper Res Soc50(10):1071–1078

17.Liao CJ,Chen WJ(2003)Single-machine scheduling with periodic

maintenance and nonresumable cee02d639b6648d7c1c74632puter Operation Research 30:1335–1347

18.Sbihi M,Varnier C(2008)Single-machine scheduling with

periodic and flexible periodic maintenance to minimize maximum cee02d639b6648d7c1c74632puter Industrial Engineering55(4): 830–840

19.Chen W(2007)An efficient algorithm for scheduling jobs on a

machine with periodic maintenance.Int J Adv Manuf Technol34 (11–12):1173–1182

20.Dekker R(1996)Application of maintenance optimization

models:a review and analysis.Reliab Eng Syst Saf51(3):229–240

21.Pinedo M(2002)Scheduling:theory,algorithms and systems.

Prentice-Hall,Englewood Cliffs

22.Vlok PJ,Coetzee JL,Banjevic D,Jardine AKS,Makis V(2002)

Optimal component replacement decisions using vibration mon-itoring and the proportional-hazards model.J Oper Res Soc53

(2):193–20223.Pan E,Liao W,Xi L(2010)Single-machine-based production

scheduling model integrated preventive maintenance planning.Int J Adv Manuf Technol50(1–4):365–375

24.Aghezzaf E,Najid NM(2008)Integrated production planning and

preventive maintenance in deteriorating production systems.Inf Sci178(17):3382–3392

25.Song DP(2009)Production and preventive maintenance control

in a stochastic manufacturing system.Int J Prod Econ119(1):101–111

26.Gebraeel N,Lawley M,Liu R,Parmeshwaran V(2004)Residual

life predictions from vibration-based degradation signals:a neural network approach.IEEE Trans Ind Electron51(3):694–700 27.Wang W,Zhang W(2005)A model to predict the residual life of

aircraft engines based on oil analysis data.Nav Res Logist52

(3):276–284

28.Banjevic D,Jardine AKS(2006)Calculation of reliability

function and remaining useful life for a Markov failure time process.IMA J Manag Math17:115–130

29.Yang ZM,Djurdjanovic D,Ni J(2008)Maintenance scheduling in

manufacturing systems based on predicted machine degradation.J Intell Manuf19(1):87–98

30.Qiu H,Lee J,Lin J,Yu G(2003)Robust performance degradation

assessment methods for enhanced rolling element bearing prog-nostics.Advanced Engineering Informatics17(3–4):127–140 31.Chen Q,Egan DM(2006)Predicting transformer service life

using simplified Perks'equation and Iowa curves.In:IEEE Power Engineering Society General Meeting

32.Gupta S,Ray A,Keller E(2006)Symbolic time series analysis of

ultrasonic signals for fatigue damage monitoring in polycrystalline alloys.Meas Sci Technol17(7):1963–1973

33.Anoop MB,Rao KB(2007)Application of fuzzy sets for

remaining life assessment of corrosion affected reinforced concrete bridge girders.J Perform Constr Facil21(2):166–171 34.Liao L,Wang H,Lee J(2008)A reconfigurable watchdog agent?

for machine health prognostics.International Journal Condition Monitoring Diagnostic Engineering Management(COMADEM) 11(3):2–15

35.Cassady CR,Kutanoglu E(2005)Integrating preventive mainte-

nance planning and production scheduling for a single machine.

IEEE Trans Reliab54:304–309

36.Lee CY,Chen ZL(2000)Scheduling jobs and maintenance

activities on parallel machines.Nav Res Logist47(2):145–165 37.Liao W,Pan E,Xi L(2008)Development of maintenance

scheduling for repairable deteriorating system.In:The proceed-ings of38th international conference on computer and industrial engineering,1–3,pp.1711–1717

38.Liao W,Pan E,Xi L(2007)Dynamic preventive maintenance

policy based on health index.In:The proceedings of2007 international conference on industrial engineering and engineering management,pp.930–934

39.Merten AG,Muller ME(1972)Variance minimization in single

machine sequencing problems.Manag Sci18(9):518–528

40.Schrage L(1975)Minimizing the time-in-system variance for a

finite jobset.Manag Sci21(5):540–543

Int J Adv Manuf Technol(2012)60:1049–10611061

本文来源：https://www.bwwdw.com/article/6ime.html