A Graph-based Ant Colony Optimization Approach for Integrated Process Planning and Scheduling☆

Jin fengWang*,Xiaoliang Fan,Chaowei Zhang,ShutingW an

School of Power and Mechanical Engineering,North China Electric Power University,Baoding 071003,China

A Graph-based Ant Colony Optimization Approach for Integrated Process Planning and Scheduling☆

Jin fengWang*,Xiaoliang Fan,Chaowei Zhang,ShutingW an

School of Power and Mechanical Engineering,North China Electric Power University,Baoding 071003,China

A R T I c L E IN F o

Article history:

Received 25May 2013

Received in revised form 14 October 2013 Accepted 16 Novem ber 2013

Available on line 6 June 2014

Process planning

Scheduling

Ant colony optimization

Makespan

This paper considers an ant colony optimization algorithm based on AND/OR graph for integrated process planning and scheduling(IPPS).Generally,the process planning and scheduling are studied separately.Due to the complexity of manufacturing system,IPPS combining both process planning and scheduling can depict the real situation of a manufacturing system.The IPPS is represented on AND/OR graph consisting of nodes,and undirected and directed arcs.The nodes denote operations of jobs,and undirected/directed arcs denote possible visiting path among the nodes.Ant colony goes through the necessary nodes on the graph from the starting node to the end node to obtain the optimal solution with the objective of minimizing makespan.In order to avoid local convergence and low convergence,some improved strategy is incorporated in the standard ant colony optimization algorithm.Extensive computational experiments are carried out to study the influence of various parameters on the system performance.

?2014 Chemical Industry and Engineering Society of China,and Chemical Industry Press.All rights reserved.

1.Introduction

Process planning and scheduling are two important aspects in manufacturing systems,which determine how and when to produce with respect to manufacturing resources.Process planning is to establish technological requirements to satisfy the specified design. Scheduling is to arrange resources available to schedule the operations. Traditionally,these two activities are performed sequentially and separately.Scheduling is conducted after the process plan is generated. However,current manufacturing environment changes fast.Especially, with the development of manufacturing technology and personalized consumer demand,modern manufacturing systems operate withincreasing complexity and flexibility.In such a system,order details, real-time status of production workshop and distribution of production facilities have an increasingly important effect on the performance of process planning and scheduling.If a process plan is carried out regardless of the scheduling objective,it may cause serious bottlenecks and obstacle to improve the productivity and responsiveness of the manufacturing systems[1].

Integrated process planning and scheduling(IPPS)is an important method to meet the need of modern manufacturing system,which optimizes the manufacturing system by combining process planning and scheduling.This paper presents the application of an improved ant colony optimization(ACO)algorithm in IPPS problem,which makes use of alternative process route as inputs of scheduling,and determines appropriate operations and process routes according to the actual status of manufacturing systems.The scheme of process planning and scheduling is achieved through choosing alternative process routes based on the ACO under the restriction of optimization targets.

2.Related Work

The preliminary idea of IPPS was introduced by Chryssolouris et al. [2,3].Nasr and Essayed presented two heuristics based on mixed integer programming to determine an efficient schedule for n jobs m machines problem with alternative machine routings for each operation to minimize the mean flow time[4].Bandeimarte and Calderinideveloped a two-phase hierarchical tabu search[5].Kim et al.gave a scheduling system with flexible process plans and presented an auction-based task assignment method between multiple parts and multiple machines [6].Kim and Egbelu proposed a mixed integer programming model for a problem with n-job,m-process plan,and k-operation IPPS to minimize the makespan of jobs[7].Saygin and Kilic proposed a frame for IPPS to reduce the completion time.In order to solve the IPPS,a heuristic method was proposed[8].Tan presented a review in the process planning and scheduling area and discussed the extent of applicability of various approaches[9].

Lee and Kim proposed an approach to the integration of process planning and scheduling using simulation based genetic algorithm s.A simulation module was used to compute performance measures based on process plan combinations and the results were fed into a genetic algorithm to improve the solution quality until the scheduling objectives were satisfied[10].Kim et al.proposed the symbiotic evolutionary algorithm(SEA)[11],which is a modified evolutionary algorithm based on the idea that parallel searches for different pieces of solution are more efficient than a single search for the entire solution.Kumar etal.attempted to use ACO for the IPPS problem,which is represented by graph with nodes and arcs.Individual ants move from the initial node to the final node through all nodes desired to be visited.The solution of the algorithm is a collective outcome of the solution found by all the ants[12].Tan and Khoshnevis presented a linearized polynomial mixed-integer programming model for IPPS[13].Wong et al.developed a multi-agent negotiation(MAN)approach for IPPS and established an agent-based framework to simulate the IPPS approach[14].Wang et al.presented a review in the distributed process planning and scheduling area[15].

Recently,some research results for the IPPS are presented.Liand McMahon used a unified model and a simulated annealing-based approach to facilitate the integration and optimization process.Three strategies,including processing flexibility,operation sequencing flexibility and scheduling flexibility,were used for exploring the search space to support the optimization process effectively[16].Moon et al. dealt with IPPS in a supply chain,formulating a mixed integer programming model for integration,which considers alternative operation sequences and precedence constraints,and developing a newevolutionary search approach based on a topological sort[17].Shao et al.developed a new integration model and a modified genetic algorithm-based approach to facilitate the integration and optimization of process planning and scheduling,and efficient genetic representation and operator schemes to improve the optimization performance of the modified genetic algorithm-based approach[18].Li et al.developed a new hybrid algorithm based approach to solve the IPPS problem and efficient genetic representation,operator and local search strategy to improve the optimization performance[19].Leung et al.presented an ACO algorithm in an agent-based system to IPPS and proposed a graph-based solution method to minimize makespan[20].Wong et al. proposed a two-stage ACO algorithm by a multi-agent system to accomplish IPPS[21].

3.Representations for Process Planning and Scheduling

3.1.Statement of problem

The IPPS problem can be described as follows[22].

Given a set of n parts to be processed on machines with operations including alternative manufacturing resources,selecting suitable manufacturing resources and making sequence of operations so as to determine a schedule in which the precedence constraints among operations can be satisfied and corresponding objectives can be achieved.

3.2.Representations for process planning and scheduling

The IPPS is a typical combination optimization problem consisting of two sub-problems,process planning and job scheduling.This paper presents an approach to solve the IPPS problem through an AND/OR graph constructed on the ACO.For each part,all of the rational operations and feasible process routes are recorded in an AND/OR graph.The AND/OR graph structure can represent a set of possible alternative process routes [23].The AND-subgraph means the priority constraints among the operations of the same parts.The OR-subgraph means the correlations among the operations of the part,which indicates that one of the alternative process routes is accessed to be visited.To app ly the ACO algorithm to construct schedules for IPPS,the AND/OR graphs is represented.Given a disjunctive graph D=(O,U,V),where O is a set of nodes representing all processing operations Oi,j,U is a set of directed arcs,which corresponds to the precedence relationships among the operations of the same parts,and V is a set of undirected arcs,which connects all possible combination of the nodes and represents the visited relations of the same or different parts[24].Both U and V rep resent possible paths for ants to travel from one node to another.The ants are free to travel along the paths constructed on the AND/OR graph. To facilitate the implementation of ACO algorithm,two dummy nodes S and E are added as the starting and ending of the node[11,19].Fig.1 is the AND/OR graph with parts A and B,in which every note indicates certain operation.O11,the first node on the left belonging to part A,stands for the first operation of part A.The corresponding processing time is 7 s on machine W1and 6 s on machine W4.Fig.1 indicates that part A includes three alternative process routes consisting of 11 operations and part B includes six alternative process routes consisting of 13 operations.All process route available consisting of the operations from the two parts can be described in detail on the AND/OR graph.

4.An Improved ACO Algorithm for IPPS

4.1.Standard ACO algorithm

Because AND/OR graph represents every available process route of all parts,ant colony cantraverse all notes on the AND/OR to achieve the solution of IPPS.Every node on the AND/OR graph signifies an operation of the job,which can be processed by different machines. The ant colony is placed on the starting node.An artificial ant visits some nodes by emulating the behavior of real ants.At the end of the continuous traversal process,a scheduling solution for the IPPS is constructed.The ants deposit amount of pheromone on the visited path consisting of nodes and arcs including directed and undirected arcs. Generally,in order to complete the traversal process,all nodes on the AND/OR have to be visited.In IPPS,due to the alternative process route of the same part represented by OR-subgraphs on the AND/OR graph,not all the nodes have to be visited[20].For example,if node O12of part A is selected,the branch including nodes O14,O15,O17,and O111will be neglected because they belong to another alternative process route.

k ants are de ployed at the starting node S initially.They are allowed to go through the whole AND/OR graph along the nodes and arcs in accordance with the precedence relationship constraints of different nodes,until a scheduling solution is generated for all parts.Due to the machine flexibility,once a node is visited by an ant,all the other nodes of the same operation but of other alternative machines will be ignored,as the nodes and arcs of the AND/OR graph are pheromone carriers.When an ant chooses the next node v among all the possible nodes connecting to current node u,the pheromone amount τuvand the heuristic desirability ηuvwill construct an important factor to guide the ant to search the optimalpath.

The heuristic desirability ηuvshall reflect the attraction of selecting the next node.It will be calculated according to the process time of current operation on the selected machine[14].The heuristic desirability ηuvcan be given as

where E is a positive constant.Eq.(1)shows that the nodes with smaller processing time have higher desirability value,which have more attraction to the ants.

The pheromone amount τuvindicates the attraction of arcs for the following ants,which specifies how good the previous scheduling solution obtained from those ants arrived at the end node are.It willbe updated according to the makespan for every ant to complete the scheduling.The pheromone amount τuvcan be given as

Fig.1.The AND/ORgraph of an IPPSproblem with two parts.

where ρ is an evaporation coefficient to arc(u,v),andis the quantity of pheromone trail on the arc(u,v)by ant k in each iteration.We also have

where Q is a positive constant and Ckis the makespan by ant k.Before ant colony begins the iteration,the pheromone amount on every arc is set to be τ0initially.

The heuristic desirability and the pheromone amount construct a probability of moving from a node from another for an ant.The more the pheromone amount on the arcs or the higher the heuristic desirability on the nodes,the higher the selective probability.For ant k,the

where α and β denote the weighting parameters controlling the relative importance of pheromone amount and heuristic desirability,respectively,and Skrepresents the set of nodes,to which the ant has an access to move.

4.2.The improved strategy generated from standard ACO

When ACO is used to solve a combination optimization problem,the performance of ant colony algorithm may not be competitive compared with the other evolutional algorithms.Usually,two obstacles have to be faced,local convergence and stagnation[24].In order to get rid of them, several improvements and modifications are suggested to improve the performance of standard ACO algorithm.If all of the ants constructalmost the same scheduling solution repeatedly at the early stage of ACO algorithm,the algorithm will fall in to local convergence.The local convergence is the extraordinary accumulation of pheromone on the arcs caused by some non-typical factors,which makes the further exploration of new paths impossible.To void the local convergence,a parameter Mrptcontrolling the repeated number of the same scheduling solution is set in advance.

To avoid the local convergence,we adopt the method of reducing the pheromone amount on the arcs and enhancing the attraction of nodes as follows.The impact coefficient of pheromone amount E is ad justed to enhance the attraction of nodes,which can be given as

where E0is the initial value of E,which is set by trial and error method according to the complexity of IPPS.

Eq.(2)shows that both pheromone evaporation coefficient ρ and coefficient of incremental pheromone Q affect the pheromone amount on the arcs,so ρ is ad justed to

where ρ0is the initial value of ρ.In order to avoid unlimited accumulation of the trail,the value of ρ is limited in[0,1].

Once the local convergence occurs,the faster the pheromone on the arc falls,the higher the probability of escaping from the local convergence for the ants.Q is ad justed to

where Q0is the initial value of Q,set by trial and error method according to the complexity of the IPPS.

In order to accelerate the convergence of the algorithm,a new pheromone updating rule is proposed.The new rule refers to repeated pheromone update of local visited arcs,on which the best schedule in current iteration by the total number of ant k is generated.When ant k completes the schedule,the pheromone mount of those arcs visited by ant k will be updated by Eq.(2).This rule referred to as“global update”consists of Eqs.(2),(3),(6)and(7).When all of the ants complete the schedule,an ant achieved the best schedule generates in the current iteration.The pheromone mount on its visited arcs will be updated again by Eq.(2).The arcs visited by the ant and achieving the best schedule in the current iteration execute twice pheromone update by Eq.(2).This rule may be referred to as“l(fā)ocal update”.The pheromone amount of those arcs will deposit fast at the early stage.Themore the pheromone amount on the arcs,the higher the selective probability of moving from a node from another node,which can accelerate the convergence of the algorithm to the near optimal solution.

5.Experiments and Results

Many parameters need to be ad justed while ACO is applied in the combination optimization.The same condition has to be faced to solve the IPPS.Those parameters include K,ρ,α,β,E0,Q0,and τ0.In order to achieve the optimal scheduling solution,it is necessary to ad just those parameters according to the complexity of IPPS.This paper takes the IPPS in Fig.1 as an example to verify the proposed ACO approach.A lot of preliminary experiments are dominated to test the effect of various parameters.In each experiment,one parameter is changed and the other parameters are fixed,and the effect of the changed parameter on the algorithm properties is analyzed at different levels.The experiment result shows that the performance of the algorithm is preferable at K=10,ρ0=0.8,α=2,β=1,E0=10,Q0=50,τ0=1,Mrpt=5, and Nite=200.The makespan turns out to be 38 by the proposed ACO approach.A Gantt chart of the result is presented in Fig.2.

Simulation experiments are extended to the large-scale IPPS problems provided by Kim et al.[25].These problems involve 18 parts with various combinations of flexibility levels.Each part consists of a minimum of 8 and a maximum of 22 operations.24 test-bed problems are constructed with the 18 parts.These problems are tested with the improved ACO and standard ACO algorithm s.

The choice of parameters is very important to the results.The method of determining these parameters is more complex than the selection method in the example in Fig.1 due to the enlargement of problemsize.In the preliminary experiments,problem 3 is taken as an example to exp lain the choices of k,ρ,α,β,E0,Q0,τ0,etc.Problem 3 is solved with different values of k∈{20,50,80,100},ρ∈{0.05,0.1, 0.25,0.5,0.8},α∈{0.5,1,5,10},β∈{0.5,1,5,10},E0∈{50,60,75, 95},Q0∈{200,300,450,650},Mrpt∈{5,10,20,50},and Nite∈{100, 500,1000,2000},and fixed value τ0=1.Experimental observation has shown that k=50,ρ0=0.8,α=1,β=1,E0=60,Q0=450, τ0=1,Mrpt=20,and Nite=500 are the best choices for these parameters.Fig.3 shows the Gantt chart problem 3 with makes pan 345.

For each problem,100 trials of simulation are carried ou t and the average resu lt is taken.The results are compared in Table 1.Columns 2,3,and 4 report the average Cmax,machine utilization,average run time among 100 runs of the improved ACO,respectively,while columns 5,6 and 7 give those of the standard ACO.Column 8 com pares the improved ACO with standard ACO in term s of average Cmax.

Fig.2.Gantt chart.

Fig.3.Gantt chart.

In Table 2,the makes pan generated by the improved ACO is compared with those of SEA by Kim et al.[11],MAN by Wong et al.[14], the agent-based ACO by Leung etal.[20],aswellas the two-stage ACO by Wong[21].Not all the problemsets con tribute to the overall improve ment.For example,the improved ACO(345.1)is superior to SEA (355.2)and two-stage ACO(366),inferior to MAN(282.6)and agent based ACO(273.8)in problem 3.However,the improved ACO(378.7) has the most optimal solution(345.1)compared to SEA(378.9),MAN (463),agent-based ACO(401.5)and two-stage ACO(398.2).Thus the improved ACO is more competitive in large scale problems.

6.Conclusions

An improved ACO algorithm is developed to integrate process planning and scheduling in this paper.Firstly,a graph-based representation for integrated process planning and scheduling is developed.The graph consists of three basic elements including set of nodes,set of arcs,and relation of AND/OR,which respectively stands for all of the processing operations,directed/undirected arcs connecting all possible nodes,and the alternative process plans of individual parts.Secondly,an approach is designed for IPPS based on the graph.In order to avoid local convergence and stagnation,several improvements are conducted to improve the performance of standard ACO algorithm.To verify the feasibility of the proposed approach,a number of simulation experiments are carried out to com pare this approach with other previously developed approaches.The experimental results show that the proposed approach can effectively generate good solutions.

Table 1Comparison of makes pan,machine utilization,and runtime for the improved ACO and standard ACO

Table 2Comparison of average makespan of different approaches

However,the improved strategy for ACO is simple.Further work is to use additional criteria to improve the performance of ACO and apply this approach to enhance the performance of manufacturing system.

Nomenclature

E impact coefficient of pheromone amount

k number of ants in each ant colony

Mrptmaximum repeated number of the same scheduling solution

m total number of machines in the process

Nitenumber of iterations

Nrptrepeated number of the same scheduling solution

n total number of jobs to be scheduled

Oijoperation j of job i(i=1,2,…,n)

Q coefficient of incremental pheromone

tijkprocessing time for operation Oijon machine k(k=1,2,…,m)

u source nodes

v possible destination nodes

α weighting parameters of ηuv

β weighting parameters of τuv

ηuvheuristic in formation on the arc from u to v

ρ pheromone evaporation coefficient

τuvpheromone in formation on the arc from u to v

[1]R.Shafaei,P.Brunn,Workshop scheduling using practical(inaccurate)data.Part3:a framework to integrate job releasing,routing and scheduling functions to create a robust predictive schedule,Int.J.Prod.Res.38(1)(2000)85-99.

[2]G.Chryssolouris,S.Chan,W.Cobb,Decision making on the factory floor:an integrated approach to process planning and scheduling,Robot.Com put.Integr. Manuf.1(3-4)(1984)315-319.

[3]G.Chryssolouris,S.Chan,An integrated approach to process planning and scheduling, CIRP Ann.Manuf.Technol.34(1)(1985)413-417.

[4]N.Nasr,A.Elsayed,Job shop scheduling with alternative machines,Int.J.Prod.Res. 28(9)(1990)1595-1609.

[5]P.Bandemarte,M.Calderini,A heuristic bicriterion approach to integrated process plan selection and job shop scheduling,Int.J.Prod.Res.33(1)(1995)161-181.

[6]K.H.Kim,J.Y.Song,K.H.Wang,A negotiation based scheduling for item s with flexible process plan,Com put.Ind.Eng.33(3-4)(1997)785-788.

[7]K.H.Kim,P.J.Egbelu,A mathematical model for job shop scheduling with multiple process plan consideration per job,Prod.Plan.Control9(3)(1998)250-259.

[8]C.Saygin,S.E.Kilic,Integrating flexible process plans with scheduling in flexible manufacturing systems,Int.J.Adv.Manuf.Technol.15(4)(1999)265-280.

[9]W.Tan,Integration of process planning and scheduling—a review,J.Intell.Manuf. 11(1)(2000)51-63.

[10]H.Lee,S.S.Kim,Integration of process planning and scheduling using simulation based genetic algorithms,Int.J.Adv.Manuf.Technol.18(8)(2001)586-590.

[11]Y.K.Kim,K.Park,J.Ko,A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling,Com put.Oper.Res.30(8)(2003) 1151-1171.

[12]R.Kumar,M.K.Tiwari,R.Shankar,Schedu ling of flexible manufacturing systems:an ant colony optimization approach,P.I.MECH.ENG.B-J.ENG.217(11)(2003) 1443-1453.

[13]W.Tan,B.Khoshnevis,A linearized polynomial mixed integer programming model for the integration of process planning and scheduling,J.Intell.Manuf.15(5)(2004) 593-605.

[14]T.N.Wong,C.W.Leung,K.L.Mak,R.Y.K.Fung,An agent-based negotiation approach to integrate process p lann ing and scheduling,Int.J.Prod.Res.44(7)(2006) 1331-1351.

[15]L.H.Wang,W.M.Shen,Q.Hao,An overview of distributed process planning and its integration with scheduling,Int.J.Com put.Appl.Technol.26(1-2)(2006)3-14.

[16]W.D.Li,C.A.McMahon,A simulated annealing-based optimization approach for integrated process planning and scheduling,Int.J.Com put.Integr.Manuf.20(1) (2007)80-95.

[17]C.Moon,Y.H.Lee,C.S.Jeong,Y.S.Yun,Integrated process planning and scheduling in a supply chain,Com put.Ind.Eng.54(4)(2008)1048-1061.

[18]X.Y.Shao,X.Y.Li,L.Gao,Ch.Y.Zhang,Integration of process planning and scheduling—a modified genetic algorithm-based approach,Com put.Oper.Res.36(6)(2009) 2082-2096.

[19]X.Y.Li,X.Y.Shao,L.Gao,W.R.Qian,An effective hybrid algorithm for integrated process planning and scheduling,Int.J.Prod.Econ.126(2)(2010)289-298.

[20]C.W.Leung,T.N.Wong,K.L.Mak,R.Y.K.Fung,Integrated process planning and scheduling by an agent-based ant colony optimization,Com put.Ind.Eng.59(1) (2010)166-180.

[21]T.N.Wong,S.C.H.Zhang,G.Wang,L.P.Zhang,Integrated process planning and scheduling—multi-agent system with two-stage ant colony optimization algorithm,Int.J.Prod.Res.50(21)(2012)6188-6201.

[22]Y.W.Guo,W.D.Li,A.R.Mileham,G.W.Owen,Applications of particle swarm and optimization in integrated process planning and scheduling,Robot.Com put.Integr. Manuf.25(2)(2009)280-288.

[23]Y.C.Ho,C.L.Moodie,So lving cell formation problems in a manufacturing environment with flexible processing and routing capabilities,Int.J.Prod.Res.34(10) (1996)2901-2923.

[24]M.Dorigo,V.Maniezzo,A.Colorni,The ant system:optimization by a colony of cooperating agents,IEEETrans.Syst.Man Cybern.Syst.26(2)(1996)29-41.

[25]Y.K.Kim,A set of data for the integration of process planning and job shop scheduling,Available at/http://syslab.chonnam.ac.kr/links/data-pp&s.doc 2003.

☆Supported by the Fundamental Research Funds for the Central Universities (13MS100),the HebeiProvince Research Foundation of NaturalScience(E2011502024) and the NationalNaturalScience Foundation of China(51177046).

*Corresponding author.

E-mailaddress:wm 803@sohu.com(J.Wang).