Proceedings of the 2009 IEEE International Conference on Robotics and Biomimetics December 19 -23, 2009, Guilin, China
Hybrid Nested Partitions Algorithm for scheduling in job shop problem
Wei Wu, Junhu Wei, and Xiaohong Guan, Fellow, IEEE SKLMS Lab, MOE KLINNS Lab and the Systems Engineering Institute Xi’an Jiaotong University
Xi’an, Shanxi 710049, China (mr.allawn@gmail.com)
Abstract—this paper introduces the main idea of Nested Partitions algorithm, and applied it to solve the job shop scheduling problem. In the algorithm the job shop scheduling problem is considered as a partition tree. The algorithm partitions the feasible region and concentrates the sampling effort in those subsets of feasible regions that are considered the most promising. Genetic algorithm search is incorporated into the sampling procedure, and use the sample points to estimate the promising index of each region. Computation experiments indicated that the hybrid algorithm outperforms the constructive GA search in goodness of searching.
Index Terms—nested partitions, genetic algorithm, job shop scheduling, combinatorial optimization
I. INTRODUCTION
The Nested Partitions (NP) algorithm is a new optimization algorithm, and has been proven to be a useful framework for effectively solving large-scale discrete optimization problem [1]. The NP framework allows us to incorporate many efficient heuristics such as the tabu search and genetic algorithm into its procedure. The resulting hybrid algorithms are more efficient than either generic NP or the heuristics alone. Domain knowledge and the special structure of the problem can be utilized in the NP procedures, such as biased sampling. The NP method can also be combined with math programming to produce more efficient search algorithms when the math programming approach alone fails to solve the problem. A few successful NP applications are summarized by Shi etc., such as Product Design, Buffer Allocation, Supply Chain Optimization, Feature Selection, Resource Constrained Project Scheduling, Radiation Treatment planning, Intermodal Hub Location Problems[2-5].
Job shop scheduling (JSS) is regarded as a NP-hard problem. Even in the NP-hard class of problems, JSS appears to belong to the more difficult ones. A number of algorithms have been developed to address this task. These include the Giffler and Thompson algorithm, the shifting bottleneck algorithm, tabu search (TS) [6], simulated annealing (SA) [7]
This work was supported in part by the National Natural Science Foundation (60736027, 60704033), the 863 High Tech Research and Development Program (2007AA04Z154) and the Natural Science Research Program of Shanxi Province (2007F41) of china.
and genetic algorithm (GA) [8] etc. In this paper, job shop scheduling based on Nested Partitions algorithm is discussed, included scheduling partitioning scheme, sampling scheme, selection region scheme, backtracking strategy. The remainder of the paper is organized as follows. In section 2 we review the JSS problem and in section 3 we introduce the NP algorithm. Section 4 describes a detailed application of hybrid algorithm to the JSS problem and the computational results are presented in section 5. Finally section 6 contains some concluding remarks and plans for future research.
II. JOB SHOP SCHEDULING PROBLEM
A specific and well known class of scheduling problems is the job shop scheduling problem. In these problems there are n jobs and m machines. Each job has an operation assigned to every machine that must be performed in a specific order. Every operation must wait for the previous operation on that machine and the previous operation within its job to be completed before it can start to run.
A n×m job shop scheduling problem can be described that n jobs need to be processed on m machines, the processing sequence of jobs is defined in advance, and each operation of a job has its own processing time. Each machine can only process one job at the same time; each operation can’t be interrupted. One of the objective functions for job shop scheduling problem is the minimum makespan. The JSS problem can then be formulated as the following mixed integer problem. The decision variables are defined as [9]
a =1 ifmachinehprocessesjobibeforemachinek; i h k ® ̄ 0 e l s e .
1 ifmachinekprocessesjobibeforejobj; xijk = ®0 else.
Let h, k denote the serial number of machine; i, j denote the serial number of job; cik denotes the completed time of job i
on machine k; pik denotes the processing time on machine k; M is a considerable large positive number.
Min max maxcik (1) {}
s.t.
978-1-4244-4775-6/09/$25.00 © 2009 IEEE.
171
̄
1≤k≤m 1≤i≤n
cik −pik +M(1−aihk)≥cih
cjk −cik +M(1−xijk)≥pjk (3)
c ik ≥ 0
i, j =1,2,4,n (5) h,k =1,2,4,m (6)
III. THE NESTED PARTITIONS ALGORITHM
For completeness we describe in this section the Nested Partitions (NP) algorithm. It systematically partitions a solution space into smaller subregions and directs most computational efforts towards the most promising regions. The following definitions will be used to illustrate it [10]. In general the optimization problem considered in this paper is as follows. Given a finite feasible region Θ , and a
performance measure J : Θ → R , solve minJ(θ).
θ∈Θ
Singleton region. A valid region is a set constructed using a fixed method of partitioning. The collection of all valid
regions is denoted by Σ . We let denote Σ0 ⊂ Σ the
collection of all such valid regions that contain only a single solution.
Surrounding region. In the k-th iteration there is a region σ(k) that is considered the most promising. What remains
of the design space Θ \ σ (k ) , is aggregated into one region called the surrounding region.
Superregion. If a valid region σ ∈Σ is formed by partitioning a valid region η ∈ Σ , then σ is called a subregion of regionη . And region η is called a superregion of region σ . We define the superregion function s : Σ → Σ as follows. Ifσ∈Σ\Θ, definess(σ)=η∈Σ. For completeness we define s(Θ) = Θ .
Depth. We define the depth d : Σ → N0 , Θ have depth zero, subregions of Θ having depth one, and so forth. Since
they cannot be partitioned further, we call the singleton region in Σ0 regions of maximum depth.
Promising Index. The local search information is incorporated into a promising index function I : Σ → R that is used to determine how the global search is concentrated in the next iteration. A set function is a valid promising index
(PI)isandonlyifforallσ ={θ}∈Σ0 haveI(σ)=J(θ). So the method can be briefly described as follows [11]. In the k-th iteration, the region σ (k ) considered most promising is assumed. We then partition this region into Mσ (k ) subregions and aggregate the entire surrounding
region Θ\σ(k) into one. Therefore, only Mσ(k) +1
disjoints subsets cover the feasible region. Each of these regions is sampled using some sampling scheme, and a promising index is calculated. These promising indices are then compared to determine which region is the most promising in the next iteration. However, if the surrounding region is found to be best, the algorithm backtracks. The NP algorithm divides into four main steps and each of these steps can be implemented in a generic fashion.
(2)
(4)
172
Partitioning. Ifσ(k)∉Σ0 , partition the most promising region σ (k ) into M subregions, and aggregate the
σ (k)
surrounding region Θ\σ(k) into one region,
denoted σ (k) . The partitioning strategy imposes a Mσ ( k ) +1
structure on the feasible region and is very important for the convergence of the algorithm.
Sampling. Randomly sample Nσ j ( k ) points from each of theregionsσj(k),
θ j1 ,θ j2 ,3,θ jN j , j =1,2,3,M
And calculate the corresponding performance values
σ(k)
J(θj1),J(θj2),3,J(θjNj ),j=1,2,3,M
+1.
σ (k)
This can be done in almost any fashion. The only condition is that each schedule in a given sampling region should be
selected with a positive probability.
Estimation of the Promising Index. Once each region
has been sampled the next step is to use the sample points to estimate the promising index of each region.
I (η ) = lim J (θ ) . θ ∈η
The only requirement imposed on a promising index is that it agrees with original performance function on regions of maximum depth. Due to the simplicity of this requirement, many local search heuristics can be used in this step to construct a promising index.
Backtracking. If the surrounding region has the best promising index the algorithm backtracks. This can be done in several manners, two of which will be discussed in these papers. The first is backtracking all way to the entire feasible regionσ(k+1)=Θ.Thesecondistobacktracktoaregion
of one less depth than the current most promising regionσ (k +1) = s(σ (k)) .
IV. THE HYBRID NESTED PARTITIONS ALGORITHM
The scheduling representation of the hybrid NP algorithm is illustrated in Fig. 1.
+1.
σ=Θ d=0
o1
o2
In the k-th iteration
Partition σ(k)intoMσ(k) subregions Aggregate surrounding region Θ \ σ (k ) into one d ( σ ( k ) ) = d (σ ( k ) ) + 1
o2
o5
o2
o3
o2
o5
o1
GA sample Mσ (k) subregions
GA sample Θ\σ(k)
Compute PI(σi (k)) fromMσ (k) subregions
Compute PI(Θ\σ(k))
YES
NO
{(o ),( ⋅ ),4,( 1
{( ⋅ ),(o2 ),4,( 5
⋅ )} ⋅ )}
PI(σi (k)) better than PI(Θ\σ(k))
STOP
YES
Report Best Solution
Fig. 2. Partitioning tree for 3× 2 JSS problem
Each subregion corresponds to scheduling one of the operations in the partitioning tree. The depth one subregions are therefore defined by the following n sets.
σ * = Best Region from Mσ (k ) subregions σ(k)=σ*
d =d(σ*)
Backtrack
σp =Parentofσ(k) σ (k) =σ p
d = d (σ p )
NO
{( ⋅ ),( ⋅ ),4,(on×m )}
The depth d = n regions are similarly defined by fixing n
elements and so forth. Let NU (σ (k)) denote the set of unscheduled jobs in the subregionσ(k). Note that the
maximum depth will be equal to the number of jobs. The number of subregions at each level in the partitioning tree is variable and decreases as the depth increases. The NP method
must maintain at most n − d (σ (k )) subregions in any iteration.
B. Scheduling sampling scheme
The next step of the algorithm is to sample from each of the subregions and from the aggregated surrounding region. If the sampling strategy tends to favor good schedules the algorithm is more likely to select the correct subregion in the next iteration and the speed of convergence will hence be increased. Assume that a region σ ∈Σ is being sampled,
then d (σ ) operations have already been assigned and
n − d (σ ) operations have not been fixed. In this paper, we
use the genetic algorithm (GA) to sample. Based on the mechanics of artificial selection and genetics, a GA combines the concept of survival of the fittest among the solutions. A GA repeats evaluation, selection, crossover, and mutation after initialization until the stopping condition is satisfied. In our research and experiments, we designed a routine of the GA sampling scheme as the following.
Design chromosome. The primary determinants of a GA’s success or failure are the coding chromosome. Better chromosome representation is well designed; no infeasible solutions will be produced and the algorithm could expect to be more efficient. For this reason, we design an efficient
Fig. 1. Flowchart of the hybrid NP procedure
A. Partitioning scheme
Although the NP algorithm does not limit the way in which we partition, but the specific strategies employed affect efficiency. To apply the NP algorithm, we first need to consider how to partition the solution space into several subregions that can be partitioned further until each subregion contains only a single solution. For a n×m JSS problem, a
schedule θ ∈ Θ can be written asθ =(O)={o1,o2,4,on×m}. In this paper, the schedule
θ uses a permutation with m-repetitions of job numbers. Each job number occurs m times in the scheduleθ . So the basic idea is to completely schedule one operation at each of level of the partitioning tree [12].
Consider the three jobs and two machines problem, Fig. 2 partially illustrates the partitioning tree for the job shop
problem. So at depth one, there are 3 × 2 = 6 subregions.
And a singleton region can be given as [3 2 1 13 2] . The
important feature of the singleton region is that any permutation can be decoded to a feasible schedule.
173
coding of chromosome. The encoding method is the operation-based representation encoding. This encodes a schedule as a sequence of operations and each gene stands for one operation. An example of a chromosome for a subregion σ(2) fora 3×2JSSproblemisshowninFig.3.
individuals after crossover are also all feasible, and generate the children CS1 and CS2 . Fig. 4 illustrates the crossover process of crossover operation.
PS1
PS2
o6 Fig. 3. Chromosome representation
Selection operation. The selection phase is to choose the chromosomes for reproduction. In this study, we adopt linear ranking to select the chromosomes in order to exploit the most promising regions at the end. Individuals are sorted
according to their fitness and a rank ri ∈{1,2,4,N}is assigned to each, where N is the population size. The best
individual gets rank N while the worst gets rank 1.
2r
pi = i , i=1,2,4,N
N(N +1)
is the probability of choosing the ith individual in the rank ordering.
In each generation, a number of best chromosomes are reserved to fill the entire population. During the linear ranking selection process, duplicate chromosomes are prohibited from entering the population. This can cause of rapid convergence to local optimum.
Crossover operation. To exploit the potential of the current generation, crossover operation is used to generate new individual. In order to inherit the properties of two parent solutions to two offspring solutions, the effective crossover operator proposed in this paper is described as follows. In our work, we consider two-point crossover. The crossover operation works as follows [13]:
Step 1. Select two parent individuals as PS1 and PS2
randomly from the subregionσ(k). And randomly pick a
value α(n×m−d(σ(k))) as cross block. The cross block
length is controlled using parameter α and 0 ≤ α ≤ 1 . Hence, as α increases, the crossover operation has a greater effect on the GA algorithm.
Step 2. Swap the cross block in parent PS1 and PS2 . And generate two temp individuals TS1 andTS2 .
Step 3. Find out the exceeded genes form TS1 and TS2 by comparing the cross block. For we only change these genes,
their preceding constraints are not be changed. Therefore, the
TS1
TS2
CS1
CS2
o3 o4 o5
Fig. 4. Example of crossover operation
Mutation operation. The swap-change method is used in the mutation operation. Usually, mutation is applied with small probability. Large probability may destroy the well chromosome. If one chromosome is to be mutated in subregionσ(k), then two positions are randomly generated
in [d(σ(k)),n×m]to be exchanged. According to the chromosome design, the new individual is a feasible solution.
C. Select Promising Index scheme
The promising index of the algorithm is the best sampled found at each subregion and agrees with the original performance function on regions of maximum depth, i.e., on singletons. So in this paper, the promising index of each subregion is taken as
I(η) = arg{max{cn×m}}→ min
The subregion having the minimum promising index is considered as the most promising subregion. Shi etc. have shown that the NP algorithm above generates a Markov chain
and under certain regularity conditions θopt is the singleton
state that has the largest stationary probability. Let
Nk (σ ) denotes the number of times each maximum depth
region has been visited. In each of the iteration, an estimate of stationary distribution is generated,
μ (σ ) = N k (σ ) , σ ∈ Σ kk
And this estimate converges asymptotically to the true stationary distribution. Therefore, the NP algorithm converges to the global optimum.
D. Scheduling backtracking scheme
If the index corresponds to the surrounding region, then backtrack to a large region containing the current most promising region. In this paper we consider backtracking to
174
the superregion of the current most promising region. That is, letσ (k +1) = s(σ (k)) . Shi etc. has shown the NP method
generates a Markov chain. Therefore, the method can be considered a Monte Carlo sampler that samples from the stationary distribution. And derive a stopping criterion for the method.
V. COMPUTATIONAL RESULT AND ANALYSIS
In order to test the performance of our hybrid nested partitions algorithm, some benchmark instances are selected to simulation, including FT, ORB, ABZ and LA [14-15]. These instances can be downloaded from http://mscmga.ms.ic.ac.uk. For the benchmarks, the hybrid nested partitions procedure was developed for solving the JSS problem. The computation results obtained with the JSS benchmarks have shown that our proposed the hybrid nested partitions algorithm can be applied to obtain the optimal solution or near optimal solution. The proposed algorithm was implemented in GCC and computational tests were carried out on a PC Pentium 1.8 GHz and 1 GB of RAM. In our experiment, we tested different values for a list of parameters to implement the hybrid algorithm. The main parameters were set as follows. The population size for each subregion is (n×m−d(σ(k)))×S/n×m . The
population size for the initial region Θ is S . The crossover and mutation strategy have been introduced. The crossover rate and mutation rate are respectively β andγ . Each test
ofS,α, βandγ. In this paper, two sets of experiments
were designed to verify the effectiveness of the hybrid NP algorithm. The parameter values of the first experiment areα=0.5, β=0.8andγ=0.1. n and m denote respectively number of jobs and number of machines. The experimental results are displayed in table I and the test problems were run 10 times consecutively. The pure GA is implemented with same parameters as the GA search in the hybrid algorithm. The second experimental results of the benchmark problem LA26 for variable parameter values are shown in table II. The convergence cure comparison for the computational results of the best schedule for LA26 is draw as Fig. 5. By comparing the experimental results in table I, we can see that the results of the hybrid nested partitions algorithm are much better than those of a simple GA. This is mainly due to the NP algorithm imposes a structure on the feasible region. If the structure is such that good solutions tend to be clustered together, the NP method is likely to rapidly concentrate the search in these regions and converge quickly. The converge speed of hybrid algorithm enhanced obviously in Fig. 5. That is because the hybrid algorithm improved the search capability. By comparing the experimental results in table II, we can see that the results and efficiency of the hybrid algorithm also depend on the parameter values of the sampling scheme. It is observed during the development of the proposed algorithm that, having a high quality sampling scheme parameters would improve the solution quality.
problem type is therefore defined by specifying the values TABLE I
THE COMPUTATIONAL RESULTS NP+GA
S Best 930 100 946
1165 100 1173 1059 100 1103 888 100 891 1005 100 1044 1005 100 1019 887 100 890 1234 100 1242 943 100 946 656 200 678 666 50 666 926 50 926 1222 100 1222 945 100 946 1046 150 1068 1218 200 1218 1784 300 1784 1268 200 1292
GA Average
Best known
Problem
FT06 FT10 FT20 ORB1 ORB2 ORB3 ORB4 ORB5 ABZ5 ABZ6 ABZ7 LA01 LA06 LA11 LA16 LA21 LA26 LA31 LA36
n,m
6,6 55 50 55 55 0.1
Average CPU Time/s
Average
Average Best CPU Time/s
10,10 20,5 10,10 10,10 10,10 10,10 10,10 10,10 10,10 20,15 10,5 15,5 20,5 10,10 15,10 20,10 30,10 15,15
951
1178
1106
900
1049
1028
901
1250
948
689
666
926
1222
951
1073
1227
1784
1299
128 120 150 157 163 63 185 37 43 399 0.17 0.18 0.14 39 86 281 56 311
55 55 0.17 967 977 190 1199 1204 218 1135 1141 186 914 917 129 1099 1114 189
1052 1063 86 945 966 201 1269 1274 69
967 976 82 728 736 372 666 666 0.3 926 926 0.29 1222 1222 0.45 972 979 69
1112 1116 81 1251 1260 298 1796 1801 66 1359 1369 249
175
TABLE II
THE COMPARED RESULTS OF THE LA26
REFERENCES
[1] L.Y. Shi, S. Olafsson, “Nested partition method for global optimization,” Operations research, vol. 48, no.3, pp.390–407, 2000.
[2] L.Y. Shi, S. Olafsson, and Q. Chen, “An optimization framework for product design,” Management Science, vol. 47, no. 12, pp. 1681-1692, 2001.
[3] L.Y. Shi, S. Men, “Optimal buffer allocation in production lines,” IIE Transaction, vol. 35, pp. 1-10, 2003.
[4] L.Y. Shi, R.R. Meyer, M. Bozbay, A.J. Miller, “A nested partitions framework for solving large-scale multicommodity facility location problems,” Journal of Systems Science and Systems Engineering, vol. 13, no.2, pp. 158-179, 2004.
[5] S. Olafsson and J. Yang, “Intelligent partitioning for feature selection,” INFORMS Journal on Computing, vol. 17, no. 3, pp. 339-355, 2005.
[6] Nowicki E, Smutnicki C, “a fast taboo search algorithm for the job shop problem,” Management Science, vol. 42, no.6, pp. 797-813, 1996.
[7] P. Van Laarhoven, E. Aarts, J.K. Lenstra, “Job shop scheduling by
simulated annealing,” Operations Research, vol. 40, no. 1, pp. 113-125,
1992.
[8] F. D. Croce, R. Tadei, G. Volta, “A genetic algorithm for the job shop
problem,” Computers and Operations Research, vol. 22, no. 1, pp.
765-771, 1995.
[9] D. Applegate, W.Cook, “A Computational Study of the Job-Shop
Scheduling Problem,” ORSA Journal on Computing, vol. 3, no. 2, pp.
149-156, 1991.
[10] S. Olafsson, L.Y. Shi, “Ordinal Comparsion via the Nested Partitions
Method,” Discrete Event Dynamic Systems, vol. 12, no. 1, pp. 211-239,
2002.
[11] L. Y. Shi, S. Olafsson, Q. Chen, “a new hybrid optimization
algorithm,” Computer&Industrial Engineering, vol. 36, no. 1, pp.
409-426, 1999.
[12] S. Olafsson, L.Y. Shi, “A method for scheduling in parallel
manufacturing systems with flexible resources”, IIE Transactions
Research, vol. 32, no. 1, pp. 135-146, 2000.
[13] G. Shi, “A genetic algorithm applied to a classic job-shop scheduling
problem,” International Journal of Systems Science, vol. 28, no. 1, pp.
25-32, 1997.
[14] Byung Joo Park, Hyung Rim choi, Hyun Soo Kim, “A hyrid genetic
algorithm for the job shop scheduling problems.” Computer&Industrial
Engineering, vol. 45, pp. 597-613, 2003.
[15] MasatoshiSakawa,TetsuyaMori,“Anefficientalgorithmforjob-shop
scheduling problems with fuzzy processing time and fuzzy duedate,” Conputers&Industrial Engineering, vol. 36, pp. 325-341, 1999.
αβγ 0.5 0.8 0.1
0.5 0.6 0.2 0.5 0.4 0.3 0.7 0.8 0.1 0.7 0.6 0.2 0.7 0.4 0.3 0.3 0.8 0.1 0.3 0.6 0.2 0.3 0.4 0.3
NP+GA Best Average
Average CPU Time/s 281
1218 1227
1222 1234 273 1246 1256 434
1218 1228
1222 1229 374 1247 1260 464
1223 1234
1229 1238 291 1249 1257 415
323
265
Fig. 5. The computational results of the best schedule for LA26
VI. CONCLUSION
This paper presents a hybrid nested partitions algorithm combining genetic algorithm in sampling scheme for the JSS problem. The major part of this work is a generic partitioning scheme was implemented and the pure GA algorithm was incorporated into the NP method framework, which guarantees global convergence under certain conditions. These two algorithms are combined in a novel way and the hybrid algorithm retains the benefits of the both algorithms. Simulation results support our theoretical results and illustrate that the hybrid nested partitions algorithm work as designed. So the hybrid nested partitions algorithm is very efficient and potentially useful in solving the JSS problem.
Furthermore, the hybrid algorithm in this paper can be potentially all pied to some other problem, such as flow shop problem with flexible resources, flexible job shop scheduling problem, remanufacturing systems with flexible resources, etc. Based on different problem structures, some other techniques can be combined to improve the performance of the hybrid algorithm.
176