Scheduling Multiple Orders per Job with Multiple Constraints on Identical Parallel Machines

WANG Teng( ),ZHOU Bing-hai()

School of Mechanical Engineering,Tongji University,Shanghai 201804,China

Introduction

To improve the performance of the equipments in 300-mm semiconductor fabrication plants,the front opening unified pods (FOUPs) are used to store 300-mm diameter wafers[1].For scheduling the wafers effectively,semiconductor manufacturers often need to group orders from different customers into one FOUP.Once multiple orders are grouped into the same FOUP,these FOUPs must be scheduled on the machines.The resulting class of problems is called multiple orders per job (MOJ) scheduling problems[2].To match the scheduling terminology,a wafer is called as an item and an FOUP as a job.

MOJ scheduling problems as non-deterministic polynomial-time hard (NP-hard) problems in wafer fabrication processes are receiving increasing attention throughout industrial and academic world.Various achievements[2-4]which focus on MOJ scheduling problems in a single machine have been made,but there is still a lack of researches on multiple machines.Laubetal.[5]analyzed the simplified two-machine flow-shop MOJ scheduling problem ignoring the realistic factors such as ready times.Jampanietal.[6]studied the MOJ scheduling problem of parallel machines with ready times in a lot processing environment.Junetal.[7]formulated a mixed-integer program model and proposed a number of polynomial-time heuristic approaches to solve the MOJ scheduling problem of parallel machines with the presence of order ready times.

The aforementioned literatures focused on the cases of a single wafer product type.MOJ scheduling with multiple product types possesses two characteristics: (1) only orders belonging to the same product type can be grouped into a job,and (2) the setup times between jobs of different product types should be considered.Due to the special constraints,most research results of a single product type cannot be directly applied to settling the MOJ scheduling problems with multiple product types.To date,there are few works on MOJ scheduling problems containing diverse wafer product types.

The deterioration effect occurs so that production facilities become less efficient after running for a long time and the production rate decreases.As a result,a job processed later will consume more time[8].Thus,it’s important to discuss the MOJ scheduling problems with deterioration effects.Based on the analysis above,the total weighted earliness-tardiness penalties scheduling problem is studied with simultaneous considerations of diverse wafer product types,the past-sequence-dependent (p-s-d) setup times,and the deterioration effects on identical parallel machines.

1 Problem Description

The MOJ scheduling problem of parallel machines consists of job formation,job assignment,and job scheduling.Job formation is the process of combining orders into jobs,while the job assignment phase assigns jobs to machines,and the job scheduling phase sequences the jobs on the same machine.An illustrative example is shown in Fig.1.There’re five orders includingO1,O2,…,andO5，and two product types including ① and ②.With the jobs’ (FOUPs) capacity of 3 wafers,the five orders are formed into three jobs,namely,J1,J2，andJ3，whereJ1={O1}，J2={O2,O3,O4}，andJ3={O5}.These three jobs are processed on two identical parallel machines,includingM1={J2,J3} andM2={J1}.Finally,assuming that the two jobs processed onM1are in the sequence ofJ3andJ2.

In order to form the precise problem domain of the MOJ scheduling problem of parallel machines,the following assumptions are given.(1) Orders cannot be split into suborders.(2) Wafers of individual orders are of the same product type,but different orders may differ in product types.(3) Orders of individual jobs are of the same product type.(4) Both individual order sizes and the collective sizes of orders placed in the same job cannot exceed FOUP capacity.(5) The jobs are sufficient in number and the selected FOUPs can be effectively used.(6) A job should be exactly assigned to one machine and each position on the same machine also should only have one job.(7) The process of deterioration can be modeled as a non-stationary gamma process.(8) The setup time is considered as the linear p-s-d setup times.(9) The machines are continuously working except when shifting jobs.(10) The orders placed in the same job own the same completion time.(11) The earliness and tardiness costs are considered.

To state the problem clearly,the following notations are defined:

Mistherelativelargepositivenumber；Nisthenumberoforders；KistheFOUPcapacity；φisthenumberofproducttypes；?isthenumberofjobsinscheduling；θkisthenumberofpositionsatmachinek，whichisequaltothenumberofjobsassignedtomachinek；misthenumberofmachines；λilis1iforderibelongstotheproducttypel，0otherwise；fiistheproducttypeoforderi；niisthesizeoforderi；diistheduedateoforderi；wiistheweightoforderi；ρfiisthestandardunitlotprocessingtimefortheproducttypefi；ρfi0isthestandardunititemprocessingtimefortheproducttypefi；aistheunitpenaltyforearliness；bistheunitpenaltyfortardiness(a

According to assumptions (1)-(5),we can get the following relations on the basis of Ref.[9].

(1)

(2)

fi≤fi′+M(2-Xi j-Xi′j),i,i′=1,2,…,N,i≠i′;

j=1,2,…,φ,

(3)

fi≥fi′-M(2-Xi j-Xi′j),i,i′=1,2,…,N,i≠i′;

j=1,2,…,φ,

(4)

(5)

(6)

(7)

Uj+1≤Uj,j=1,2,…,φ-1.

(8)

Relation (1) ensures that an order should be assigned to exactly one job.Relations (2)-(4) guarantee that only orders which own the same product type can be assigned to the same job.Relation (5) restricts that the customer order sizes placed in the same job cannot exceedK.Relations (6)-(8) enforce that none of the jobs involved in scheduling should be empty.

Corresponding to assumption (6),the following relations are obeyed.

(9)

(10)

On the basis of assumption (7) and Ref.[10],the deteriorating processing time of jobjat positionron machinekis calculated by the following equations.

r=1,2,…,θk,

(11)

sj k1=0,j=1,2,…,φ,k=1,2,…,m,

(12)

r=2,3,…,θk.

(13)

According to assumption(8),the setup times are considered as the linear p-s-d setup times,and relations are given as follows.

hj k1=0,j=1,2,…,φ,k=1,2,…,m,

(14)

hj kr=γvkrr′sj kr,j=1,2,…,φ,k=1,2,…,m,

r=2,3,…,θk,r′=r-1.

(15)

Based on assumption (9),the actual processing time of a job is the total standard processing time of the wafers in the job,plus the setup time and the deteriorating processing time.Equations (16) and (17) define the actual processing time in lot and single item environments,respectively.

k=1,2,…,m,r=1,2,…,θk,

(16)

(17)

Corresponding to assumption (10),the completion time of orderiis calculated as follows.

(18)

The earliness and tardiness of an order determined by its completion time are shown in Eqs.(19)-(20),accordingly.

Ei=max(0,di-Ci),i=1,2,…,N,

(19)

Ti=max(0,Ci-di),i=1,2,…,N.

(20)

Corresponding to assumption (11),the objective is to minimize the total weighted earliness-tardiness penalties.

(21)

Consequently,a non-linear programming problem is formulated that takes relation (21) as the objective function and relations (1)-(20) as the constraints.

2 Algorithm Design

On the basis of the non-linear programming model,an immune genetic algorithm (IGA) which introduces immune mechanism into genetic algorithm (GA) is put forward.Compared IGA with the standard GA,the former can avoid the problem of “premature convergence” and prevent the degradation of the optimal solution effectively[11].To describe the algorithm exactly,we make the following definitions.

Definition3LetR1,R1∈R,denote the initial population andzbe the population size.

Definition4A vaccine represents some features of the optimal solution which are estimated by experience or the analysis for the problem.

(22)

The proposed algorithm consists of five key processes: encoding,initialization operator,affinity evaluation,genetic operator,and immune operator.The details of the algorithm are as follows.

Step 1: encoding

Step 1.1: genes encoding

The encoding scheme makes the genes contain more information than the ones generated by other two encoding methods proposed by Sobeykoetal.[3]and Quetal.[12]By utilizing the sufficient information,in the subsequent operations of the algorithm we can get the feasible solutions more easily.The natural encoding scheme is employed to make the algorithm simple,applicable,and convenient in operation.

Step 1.2: antibody encoding

Step 2: initialization operator

Step 2.3: generatezantibodies by repeating steps 2.1-2.2 and form the initial populationR1.

Step 3: vaccine extraction

Through the analysis for the problem domain and the experience that apparent tardiness cost with setups (ATCS) rule always can improve the solution quality of the scheduling problems with setup times and the objective of minimizing the total weighted tardiness[13],we develop the urgency-based indexIjχδ(t) for unscheduled jobjχδat timetbased on ATCS rule.The urgency-based indexIjχδ(t) is calculated by Eqs.(23)-(25) in a single item environment and by Eqs.(24)-(26) in a lot environment.The equations are described as follows:

(23)

(24)

(25)

Ijχδ(t)=

(26)

wherek1andk2are set as 2 and 1,respectively.

According to the urgency-based index,we can get the following modified ATCS rule: at timetthe job with the largest urgency-based index should be assigned to the idle machine (if more than one job has the largest index at timet,choose one arbitrarily).

Based on the analysis above,we extract the vaccine: the job sequence of the optimal solution should be in accordance with the modified ATCS rule.

Step 4: affinity evaluation

Corresponding to Eqs.(21)-(22),the fitness function is deduced as follows:

fit(rχ)=max(0,max(g(r1),g(r2),…,g(rχ),…,

g(rz))-g(rχ)),r1,r2,…,rχ,…,rz∈R.

(27)

Thus,we can compute the fitness values of the antibodies by Eqs.(11)-(20),(22),and (27).

Step 5: termination condition

Letζbe the number of iterations andζmax,ζmax∈N+be the threshold value of iterations.The initial number of iterationsζis set as 1.And ifζis equal toζmax，stop the calculation and output the results; otherwise,go to Step 6.

Step 6: genetic operator

A detailed flow diagram of genetic operator is shown in Fig.2.

Fig.2 Flow diagram of genetic operator

Step 7: immune operator

Step 7.1: vaccine inoculation

Checking the job sequences of the antibodies in the new population,if one satisfies the extracted vaccine in Step 3,conserve it; otherwise,replace it with a new sequence which is generated by applying the modified ATCS rule.

Step 7.2: immune selection of antibodies

Compare the fitness values of the parents with the ones of their offspring,replace the poor antibodies with lower fitness values,and update the population; the iteration timesζis calculated asζ=ζ+1，and then back to Step 5.

3 Experiments and Analysis

Two criteria are used to effectively evaluate IGA and the standard GA: required computation time and resulting objective function performance ratio (PR)Prproposed in Ref.[12].

The computation time is determined by the time complexity of the algorithm.The higher the time complexity is,the more time-consuming the algorithm is.

whereV(H,ζ,Y) denotes the objective function value obtained by approachH(i.e.,either IGA or GA) throughζiterations on problem instanceYandBest(Y) denotes the reference optimal objective function value on problem instanceY.We define the result obtained by IGA through 2000 iterations on problem instanceYasBest(Y).The convergence ability of an algorithm can be explained well by its PR value.The smaller the PR value is,the better the convergence performance of an algorithm is.

Both IGA and GA are implemented in the programming language C++ using Microsoft Visual Studio 2008.A computer with Intel Core 2 Duo 2.2 MHz processor and 4 GB of main memory is used to carry out the following experiments.

3.1 Parameters analysis

According to Refs.[3] and [12],the problem instances generated with 50 (or less) orders are small and medium-sized and the ones with more orders are large-sized.

Under the situation of 3 identical parallel machines,20 fifty-order instances are randomly generated for both the single unit and lot processing environments,where order sizes are uniformly distributed over the integer set [3,8] and the number of the product types is uniformly distributed over the integer set [5,10].All instances above have an FOUP capacity ofK=13.The unit penaltiesaandbare valued 1 and 2 respectively.And the values of the other parameters involved in the experiments are set following the rules described in Refs.[3] and [12-15].IGA and GA are applied to solving the problem instances and the corresponding results are shown in Figs.3-4.

Fig.3 Number of iterations versus PR

Fig.4 Number of iterations versus computation time

The numbers in Figs.3-4 depict the average values of PR and computation time computed over 20 replications,respectively.Figure 3 displays the improvement in PR as iteration times increasing.As illustrated in the figure,the results usually cannot be improved significantly after 500 iterations when using IGA approach.Running 2000 iterations potentially lead to a better result,and this small objective function performance improvement comes at the cost of increasing computation time (see Fig.4).Therefore,500 iterations will be used for IGA approach in the following experiments.As shown in Figs.3-4,IGA works surprisingly well,beating the GA.Considering that the IGA has better convergence performance,we adopt IGA to solve the following problem instances.

Similar to the method we used to determine the proper number of iterations,we carry out more experiments and obtain the proper values of other parameters (i.e.,the initial population size) to perform for IGA.

3.2 Sensitivity analysis on the relationship between computation time and the model

The proposed IGA has the time complexity ofO(z(φ3+(ζ+φ)N+m)).Obviously,the time complexity has a positive relationship with the number of the product types but doesn’t relate to the deteriorating effects and the p-s-d setup times.

3.3 Sensitivity analysis on the relationship between PR and the model

Firstly,with 5,6,7,8,9,and 10 product types generated,the experiments are running under small and medium-sized problem instances of 20,30,and 50 orders and large-sized problem instances of 100,150,and 200 orders when 3 parallel machines are taken into account.Furthermore,both the single item and lot environments are considered in the experiments.The results are shown in Figs.5-6.

Fig.5 Relationship of PR with variety of wafers in a single item processing environment

Fig.6 Relationship of PR with variety of wafers in a lot processing environment

Figures 5-6 show PR under the impact of the number of the product types for the single item and lot processing environments respectively.It can be observed that PR decreases with the increase of the number of the product types when the number of orders is invariable both in the single item and lot environments.The result is in accordance with the fact that the diversity of scheduling combinations decreases with the increasing number of the product types.Therefore,we can get the satisfying result more easily when solving the problem instancse with more product types.Considering PR values displayed in Figs.5-6,it is concluded that the performacne of IGA is stable and satisfying.

Fig.7 Relationship of PR with variety of wafers when the values of α,β,q，and change

4 Conclusions

IGA combined with the modified ATCS rule is put forward to solve the MOJ scheduling problem of parallel machines.The stable and satisfying perfomance of the results also verifies the validity of the proposed algorithm.The algorithm can be a supplement to the scheduling methods for the MOJ scheduling problems.In the furture works,the p-s-d setup times and the deterioration effects constraints on identical parallel machines can be considered as a new effort to the development of researches on MOJ scheduling problems of parallel machines.

[1] Zhou B H,Anar J M,Zheng W.Vehicle OHT Dispatching Performance Analysis of an AMHS in 300 mm Semiconductor FABs [J].JournalofDonghuaUniversity,2012,29(3): 209-214.

[2] Qu P,Mason S J.Using Tabu Search on the Single Machine Multi-orders per Job Scheduling Problem [C].IIE Annual Conference and Exhibition 2004,Houston,USA,2004: 1831-1835．

[3] Sobeyko O,Monch L.Genetic Algorithms to Solve a Single Machine Multiple Orders per Job Scheduling Problem [C].Proceedings of the Winter Simulation Conference,Piscataway,USA,2010: 2493-2503．

[4] Mason S J,Chen J S.Scheduling Multiple Orders per Job in a Single Machine to Minimize Total Completion Time[J].EuropeanJournalofOperationalResearch,2010,207(1): 70-77．

[5] Laub J D,Fowler J W,Keha A B.Minimizing Makespan with Multiple-Orders-per-Job in a Two-Machine Flowshop [J].EuropeanJournalofOperationalResearch,2007,182(1): 63-79．

[6] Jampani J,Mason S J.Column Generation Heuristics for Multiple Machine,Multiple Orders per Job Scheduling Problems [J].AnnalsofOperationsResearch,2008,159(1): 261-273．

[7] Jia J,Mason S J.Semiconductor Manufacturing Scheduling of Jobs Containing Multiple Orders on Identical Parallel Machines[J].InternationalJournalofProductionResearch,2009,47(10): 2565-2585．

[8] Yang S J.Unrelated Parallel-Machine Scheduling with Deterioration Effects and Deteriorating Multi-maintenance Activities for Minimizing the Total Completion Time [J].AppliedMathematicalModelling,2013,37(5): 2995-3005.

[9] Chen J S.Optimization Models for the Flow-Shop Scheduling Problem with Multiple Orders per Job [C].2010 40th International Conference on Computers and Industrial Engineering,Piscataway,USA,2010: 1- 6．

[10] Zhou B H,Zhai Z Q.Lifetime Distribution Model of Port Facilities with Pitting Corrosion of Stochastic Processes [C].2010 International Conference on Frontiers of Manufacturing and Design Science,Chongqing,China,2011: 46-50.

[11] Li Y P,Liu Y.Research on Vehicle Routing Problem Based on Immune Genetic Algorithm [C].2010 2nd International Conference on Information Engineering and Computer Science,Wuhan,China,2010: 1-4.

[12] Qu P,Mason S J.Metaheuristic Scheduling of 300 mm Jobs Containing Multiple Orders [J].IEEETransactionsonSemiconductorManufacturing,2005,18(4): 633-643．

[13] Pfund M,Fowler JW,Gadkari A,etal.Scheduling Jobs on Parallel Machines with Setup Times and Ready Times [J].Computers&IndustrialEngineering,2008,54(4): 764-782．

[14] Grall M E.Use of the Kolmogorov-Smirnov Test for Gamma Process [J].ProceedingsoftheInstitutionofMechanicalEngineers,PartO:JournalofRiskandReliability,2012,226(6): 624-634.

[15] Soroush H M.On the Scheduling with Past-Sequence-Dependent Setup Times and Learning Effects on a Single Machine [J].TheInternationalJournalofAdvancedManufacturingTechnology,2013,68(9/10/11/12): 2483-2487.