• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    New Hybrid Parallel Algorithm for Variable-sized Batch Splitting Scheduling with Alternative Machines in Job Shops

    2010-03-01 01:48:52ZHAOYanweiWANGHaiyanWANGWanliangandXUXinli

    ZHAO Yanwei , WANG Haiyan WANG Wanliang, and XU Xinli

    1 Key Laboratory of Mechanical Manufacture and Automation of Ministry of Education, Zhejiang University of Technology, Hangzhou 310014, China

    2 College of Computer Science and Technology, Zhejiang University of Technology, Hangzhou 310014, China

    Notations

    i —Job index,

    j —Operation index,

    k —Batch index,

    l —Machine index,

    N —Total number of jobs,

    Si—Original batch size of job i,

    ni—Total number of operations of job i,

    M —Total number of machines,

    bij—Total number of alternative machines for the jth operation of job i,

    NB—Total number of sub-batches,

    L —Length of the chromosome,

    Np—Population size,

    CR —Crossover probability,

    1 Introduction

    Under the batch production mode in a real manufacturing environment, a job consists of a batch of identical parts in the production scheduling problem, and there may exist alternative machines for operations. By splitting the original batch into many smaller sub-batches, these smaller sub-batches can be processed on different machines simultaneously, with all parts in one sub-batch processed altogether and the processing time of a sub-batch defined to be the sum of processing time of each part in that sub-batch,sharing only one set-up time, so that a faster completion can be obtained. That’s how batch splitting, also called lot streaming in many researches, arises.

    Batch splitting in flow shops can be equal (all sub-batches of a given job are of equal size), consistent(sub-batch sizes vary within a job but are the same for all machines), or variable (sub-batch sizes can change from machine to machine)[1]. And these three types of batch splitting can be applied to job shops too. Most of the existing researches on the batch splitting scheduling problem concerns the former two kinds of batch splitting.PAN, et al[2], studied the equal-sized batch splitting scheduling problem with set-up time and alternative machines, with the batch size for each sub-batch fixed in advance. SUN, et al[3], adopted a novel encoding method in genetic algorithm(GA) to optimize both the number of sub-batches for each job and the sub-batch processing order simultaneously when solving the equal-sized batch splitting job shop scheduling problem with set-up time and alternative machines. LOW, et al[4]performed comparisons between equal-sized batch splitting and consistent-sized batch splitting in the batch splitting scheduling problem with the number of sub-batches and the sizes of sub-batches fixed beforehand. MARTIN[1]proposed a heuristic to get the number of sub-batches for each job and the size of sub-batches in the consistent-sized batch splitting scheduling problem in flow shops. Although most of these researches solved the batch splitting scheduling problem by fixing the number of sub-batches, or the sub-batch sizes, or both, their achievements still provided important basis for a further study.

    On the basis of the above researches, we focus our attention on variable-sized batch splitting, trying to obtain both the optimum number of sub-bathes for each operation per job and the optimum batch size for each sub-batch in the batch splitting scheduling problem with set-up time.

    There is much scope for evolutionary algorithms for batch splitting scheduling problems. Among all kinds of evolutionary algorithms, DE is a newly-developed simple and efficient population-based heuristic, introduced by STORN, et al[5], and has been extensively investigated and improved to solve flow shop scheduling problems and job shop scheduling problems[6–9], but not including the batch splitting scheduling problem yet. Considering that the sum of values of genes in one chromosome remains the same before and after mutation in differential evolution (DE),when chromosomes are of equal length and have the same total value of genes, this paper adopts DE to solve the batch splitting problem, so that the sum of the batch sizes of all the sub-batches for any operation of any job remains the same as the original batch size of that job when values of genes in chromosomes represents batch sizes of sub-batches.

    The paper is organized as follows. The formulation for the variable-sized batch splitting scheduling problem with alternative machines is established in section 2. In section 3,a new hybrid parallel algorithm, with a global search procedure, based on self-adaptive DE and genetic crossover operator, and a problem-dependent local search procedure,is brought forward to solve both the batch splitting problem and the batch scheduling problem. Simulation and results are presented and comparisons are drawn in section 4,followed by conclusions in section 5.

    2 Problem Description and Formulation

    Consider N jobs in a scheduling system. Each job consists of a batch of identical parts, and is planed to be processed in its predefined operation sequence. And there may exist alternative machines for operations.

    To simplify the problem and make full use of alternative machines, we assume that jobs are all available at time zero,and the batch number of sub-batches for the jth operation of job i is equal to the total number of alternative machines for that operation, so that chromosomes in the algorithm can be of equal length. Each sub-batch requires one machine out of a set of its alternative machines, and a machine should be set up before it starts a processing procedure for a sub-batch.

    A mathematical model for the variable-sized batch splitting scheduling problem is developed in this paper.Values of ?ijkl, φijklandare listed as follows:

    The mathematical model is established as follows:

    Eq. (1) specifies the objective to minimize the makespan,defined by the maximum finish time of processing procedures for the latest operations. Eq. (2) ensures that the sum of the batch sizes of all the sub-batches for an operation of a job remains the same as the original batch size of that job. Eq. (3) shows that a machine is allowed to be set up for a sub-batch for an operation of a job before all the parts in the sub-batch finish the processing procedure for its predecessor operation of the same job, so that when all the parts in the sub-batch are ready, the machine can start processing procedure immediately. Note that there is an add-up notation in Eq. (3), owing to the rule presented in section 3.1 that all sub-batches within an operation of a job are sequenced in an increasing order of batch index.However, the machine starts the set-up procedure for a sub-batch only after, at least, it finishes the processing procedure for the predecessor sub-batch in the processing sequence on that machine, as is shown in Eq. (4). If the predecessor and successor sub-batches in the processing sequence on a machine are to deal with the same operation of the same job, the successor sub-batch does not need set-up procedure on that machine. Eq. (5) describes that when a sub-batch for an operation of a job needs set-up procedure, the set-up procedure couldn’t be interrupted once started. Eq. (6) provides the relationship between the start time of processing procedure and the finish time of set-up procedure for a sub-batch, which certainly specifies the sequence between the set-up procedure and the processing procedure for any given sub-batch. Eq. (7)shows that processing procedure for a sub-batch couldn’t be interrupted once started.

    3 New Hybrid Parallel Algorithm

    Fig. 1. Framework of the proposed algorithm

    3.1 Individual representation

    Parallel chromosome coding method is adopted to represent an individual, one called batch splitting chromosome, composed by batch sizes of NBsub-batches,and the other called batch scheduling chromosome,containing sequence information of NBsub-batches.

    Randomly generate bijintegers within the range [0, Si]that satisfy Eq. (2) as Sijkfor the jth operation of job i,where i = 1, 2,…, N,j = 1, 2,… , ni, and k = 1,2, …,bijAll the batch sizes of these NBsub-batches constitute the batch splitting chromosome, denoted by chromosome1,with its length L = NB, is shown as follows:

    where Sijkstands for the batch size of the kth sub-batch for the jth operation of job i. We denote Sij1Sij2… Sijbijon chromosome1 as the sub-batch size array for the jth operation of job i, where i = 1,2 , …,N andValues of zero are allowed in the batch splitting chromosome. The sequence of these NBsub-batches in chromosome1 constitutes the batch scheduling chromosome, denoted by chromosome2, with the length L. For the batch splitting scheduling problem listed in Table 1, Fig. 2 and Fig. 3 are examples for the batch splitting chromosome and the batch scheduling chromosome for the problem respectively. Genes on chromosome2 are in “ij” format, referring to the jth operation of job i, and gene “ij” appears bijtimes overall.We specify the batch index to gene “ij” according to the time “ij” appears from left to right on chromosome2, which infers that all sub-batches within an operation of a job are sequenced in an increasing order of batch index. For example, the third gene “21” on chromosome2 in Fig. 3 form left to right represents the second sub-batch for the first operation of job 2, since the gene appears the second time from left to right, and the size is 4, which can be seen from chromosome1 in Fig. 2.

    Table 1. Batch splitting scheduling problem

    All the sub-batches for the jth operation of job i are required to be sequenced ahead of any sub-batch for the j′t h operation of job i when j< j′, which means that all the sub-batches for all previous operations of a job are scheduled before any sub-batch for the current operation of that job. Then the time when parts with certain size accomplishes the processing procedure for the predecessor operation of a job can be obtained according to the completed arrangement of all the sub-batches for the predecessor operation of the job, which is needed in Eq. (3),when handling a sub-batch for the current operation of the same job.

    3.2 Fitness function

    Eq. (1) is the objective to minimize the makespan. The fitness function is designed as

    3.3 Global search procedure

    An individual is composed of a batch splitting chromosome and a batch scheduling chromosome, due to the finding that the sum of values of genes in one chromosome remains the same before and after mutation in DE and powerful optimization ability of GA for scheduling,they evolve using DE and genetic crossover operator respectively. We denote chromosome1hand chromosome2has the batch splitting chromosome and the batch scheduling chromosome from individual h respectively.

    3.3.1 Evolution procedure for the batch splitting chromosome

    A self-adaptive DE-based evolution procedure is designed for the batch splitting chromosome in this section.

    (1) Evolution procedure. A DE with block mutation and block crossover is adopted for the batch splitting chromosome, and the current population evolves according to the following steps in one cycle.

    Step 1: Set individual index h = 1.

    Step 2: For individual h in the current population,randomly generate three integers within [1, Np], denoted by d1, d2and d3, where Nprepresents the population size. d1, d2and d3are different from each other, and different from h.Carry out the evolution procedure for chromosome1 from individual h according to the following sub-steps:

    Step 2.1: Randomly generate an integer within [1, N ] as r1and another integer within [1,1rn ] as r2, and set job index i = 1 and operation index j = 1.

    Step 2.2: If i = r1and j = r2, execute step 2.3. Otherwise,execute step 2.4.

    Step 2.3: Carry out block mutation and block crossover for the sub-batch size array for the jth operation of job i on chromosome1h:

    To make sure that Si′jkis within [0, Si], the value of Kijhas to satisfy the following two equations. And we randomly choose a value that satisfies these two equations as Kij:

    Since batch sizes in this paper are integer numbers,needs a delicate modification. Set SUM = 0, and from k = 1 to k = bij, performand SUM =and if k = bij, performSUM. “[·]” means to get the nearest integer number. In this way, all thein the new array is adjusted to integer numbers, and still satisfy Eq. (2), where k = 1, 2,???, bij.Select the new array into a temporary chromosome,denoted by newchro1h. Execute step 2.5.

    Step 2.4: Randomly generate a real number within [0,1] as r3. If r3≤CR, return to step 2.3. Otherwise, select the sub-batch size array for the jth operation of job i on chromosome1hinto newchro1h, and execute step 2.5.

    Step 2.5: If j<ni, perform j = j + 1. Otherwise, perform i = i+1.

    Step 2.6: If i ≤N, return to step 2.2. Otherwise,newchro1hnow is a complete batch splitting chromosome.Put newchro1hinto the temporary population.

    Step 3: if h<Np, perform h = h + 1, return to step 2.

    (2) Adaptive crossover probability CR. To improve the performance of the algorithm, we introduced the distribution variance of fitness value ? in Ref. [10] that reflects the diversity of population to adjust the probability of crossover adaptively. ? is defined as

    wheretD represents the variance of fitness value, and

    We can see from Eq. (13) that the value of ? varies from 0 to 1, and the higher ? is, the better for the population in terms of the diversity of population. The adaptive crossover probability is designed in this paper as follows:

    The value of CR is adjusted adaptively within [CR0,2CR0] according to different value of ? when evolving.When the diversity of population degrades, meaning that the value of ? grows lower, CR is adjusted to a higher value to raise the exploration ability of the algorithm.Otherwise, when the diversity of population upgrades,meaning that the value of ? grows higher, CR is then adjusted to a lower value to improve the exploitation ability of the algorithm.

    3.3.2 Evolution procedure for the batch scheduling chromosome

    Randomly divide the current population into Np/2 groups in one cycle, with two batch scheduling chromosomes in each group, and genetic crossover operator is performed for two chromosomes in each group. Assume that two parent chromosomes in a group are denoted as chromosome2pand chromosome2q, respectively. Perform the following steps.

    Step 1: Randomly generate an integer within [1, N] as r1and another integer within [1,1rn ] as r2. Find two blocks on chromosome2pand chromosome2qthat have least number of genes but contain all the sub-batches for the r2th operation of job r1. For the problem in Table 1, if parent chromosomes are shown in Fig. 4 and r1= 1 and r2= 2,blocks covered with shadow in Fig. 4 are the blocks that have least number of genes but contain all the sub-batches for the second operation of job 1.

    Step 2: Exchange two blocks on chromosome2pand chromosome2q, and two offspring chromosomes are obtained, denoted by ch romosome2 ′pand chromosome2q′,respectively. Offspring chromosomes generated from the parent chromosomes in Fig. 4 are shown in Fig. 5.

    Step 3: Delete redundant genes and insert missing genes within the newly inserted blocks on ch romosome2 ′pand chromosome2q′. When inserting a missing gene, insert the missing gene before the genes that represent any following operations of the same job and behind the genes that represent any previous operations of the same job within the block if those genes exist in the block. The revised offspring chromosomes, denoted by newchro2pand newchro2qrespectively, are selected into the temporary population. The revised offspring chromosomes for chromosomes in Fig. 5 are presented in Fig. 6, where genes with underlines stand for the missing genes.

    3.3.3 Selection procedure

    After evolution procedures are performed for the current population, newchro1hand newchro2hconstruct a new individual h, and there are Npnew individuals in the temporary population. Select Npindividuals out of 2Npindividuals from the current population and the temporary population into the next generation through the roulette wheel selection and elitist model[11].

    3.4 Local search procedure

    An Insert-based local search method based on the individual representation proposed in this paper, is brought forward to gain a better performance. Suppose that individual h in the current population is selected to perform the local search, execute the following steps:

    Step 1: Randomly generate an integer within [1, L] as pos and a natural number within [0, 1] as r3, where L stands for the length of chromosome. Assume that the posth gene on chromosome2hfrom left to right represents the kth sub-batch for the jth operation of job i. Set g = k,= ch romosome1hand=chromosome2h.

    Step 2: If r3= 1, execute step 3. Otherwise, r3must be zero. Perform the forward search procedure:

    Step 2.1: If j>1, find the gene that representing the bi(j–1)th sub-batch for the ( j?1)th operation of job i on, and denote the position as pos1. Else, if j = 1, set pos1= ?1.

    Step 2.2: If the (pos?1)th gene onfrom left to right refers to a sub-batch for the jth operation of job i, exchange the values of Sijgand Sij(g–1)onand execute g = g?1. Execute= Insert(, pos, pos–1).

    Step 2.4: Execute pos = pos?1. If pos>( pos1+1),return to step 2.2. Otherwise, stop the local search for individual h.

    Step 3: Perform the backward search procedure:

    Step 3.1: If j<ni, find the gene that representing the first sub-batch for the ( j+1)th operation of job i onand denote the position as pos2. Else, if j = ni, set pos2 = L +1.

    Step 3.2: If the ( pos+1)th gene onfrom left to right refers to a sub-batch for the jth operation of job i, exchange the values of Sijgand Sij(g+1)onand execute g = g+1. Execute= Insert(, pos, pos+1).

    Step 3.4: Execute pos = pos+1. If pos<(pos2?1),return to step 3.2. Otherwise, stop the local search for individual h.

    In the above steps, Insert(chromosome, u, v) means to insert the gene at the uth position in the vth position on chromosome from left to right.

    3.5 Analysis of the complexity of the proposed algorithm

    Consider a batch splitting scheduling problem, with population size Npand maximal iteration number Nmaxit. In the proposed algorithm, decoding procedure, calculation procedure for adaptive crossover probability CR, evolution procedure for the batch splitting chromosomes, evolution procedure for the batch scheduling chromosomes, selection and local search are concerned in one cycle, and their time complexities are o(NpL), o(Np), o(NpL), o(0.5NpL2), o(2Np2)and o(0.2NpL) respectively. Therefore, the total time complexity for the proposed algorithm is:

    From Eq. (16), we can see that the maximal iteration number and population size, especially the length of chromosome affects the computational burden of the algorithm greatly.

    4 Experiments and Analyses

    4.1 Application of the proposed algorithm to test instances

    To evaluate the performance of the proposed algorithm,we adopt scheduling data in Refs. [2, 12–13] to construct the following four test problems:

    Problem 1 (denoted by P1): The problem is composed of 4 jobs and 6 machines, and the original batch size for each job is 8. The unit processing time for operations on alternative machines is shown in Table 2, and set-up time for an operation of a batch on a machine is equal to its unit processing time on the same machine.

    Table 2. Unit processing time for operations on alternative machines s

    Problem 2 (denoted by P2): The problem is composed of 4 jobs and 6 machines, and the original batch size for each job is 20. The unit processing time for operations on alternative machines is shown in Table 2, and set-up time for an operation of a batch on a machine is equal to its unit processing time on the same machine.

    Problem 3 (denoted by P3): The problem is composed of 6 jobs and 6 machines, and the original batch size for each job is 10. The unit processing time and set-up time for operations on alternative machines is shown in Table 3.

    Problem 4 (denoted by P4): The problem is composed of 6 jobs and 6 machines, and the original batch size for each job is 20. The unit processing time and set-up time for operations on alternative machines is shown in Table 3.

    Some related achievements concerned with these problems can be found in Refs. [2, 12–13]. The optimum makespan for P1 obtained in Ref. [12] was 87, and the optimum numbers of sub-batches were 1, 3, 5 and 4 for J1,J2, J3and J4respectively, using the proposed algorithm that first optimized the number of sub-batches for each job, and then scheduled those sub-batches based on equal-sized batch allocation method (PS: the optimum makespan in Ref.[12] for the problem with no batch splitting should be 141 instead of 140, as is shown in its gannt chart). In Ref. [2],the obtained optimum makespans for P2 were 345, 216,196 and 194 when the number of sub-batches for each job was fixed to 1, 2, 4 and 5, respectively, using equal-sized batch allocation method. P3 was solved in Ref. [13] based on the genetic algorithm and the simulated annealing algorithm, with the number of sub-batches and the sizes of sub-batches fixed in advance, and the optimum makespan was 243 for P3 with no batch splitting.

    To evaluate the performance of the proposed algorithm and confirm the effectiveness of the local search procedure and the adaptive crossover operator, we set= 200,Np=50 and CR0=0.3, and solve the four test problems. The proposed algorithm has been coded with Visual C++ .NET 2003 and runs on a PC with a Pentium 2.53 GHz processor and a 1.00 GB RAM under Windows XP 2002. The results obtained over 20 runs are shown in Table 4, where BMN,WMN, No.BMN and AvT.CPU denote the best makespan,the worst makespan, the number of the best makespan obtained among 20 runs and the average computational time in seconds over 20 runs respectively. “ALGRM1” in Table 4 refers to the hybrid parallel algorithm proposed in this paper. And “ALGRM2” is the algorithm as same as ALGRM1, except that the local search procedure is not included. “ALGRM3” is the algorithm as same as ALGRM2,except that the crossover probability CR in ALGRM3 is fixed to CR0throughout evolution.

    The increase of the size of problem from P1, P2 to P3,P4 adds to the complexity of the batch scheduling problem,while the increase of the original batch size for each job adds to the complexity of the batch splitting problem. It can be observed that the variable-sized batch splitting technique provides considerable makespan reduction, compared with results without batch splitting in Refs. [2, 12–13]. All these three algorithms can obtain excellent optimization outcomes, especially ALGRM1 and ALGRM2 that even surpass, or at least are not worse than the existing achievements in Refs. [2, 12–13]. From Table 4, we can see that ALGRM1 can always outperform the other two algorithms for all test problems in terms of optimization power, and ALGRM3 consumes least computation effort.Apparently, ALGRM1 derives great benefit from the local search procedure and the adaptive crossover operator, and provides better solutions within reasonable time limit,compared with ALGRM2 and ALGRM3.

    Table 3. Unit processing time/set-up time for operations on alternative machines s

    Table 4. Results for these four test problems through three algorithms

    The batch splitting approach in this paper tends to split the original batches into sub-batches of variable size, and compared with Ref. [2] and Ref. [12], we can get that variable-sized batch splitting is better than equal-sized batch splitting. This is probably because the variable-sized batch splitting in this paper takes care of different processing capabilities of alternative machines sufficiently,and the tradeoff between minimizing the total set-up time(achieved by reducing the number of sub-batches) and minimizing the idle time on machines (achieved by reducing batch sizes, or by increasing the number of sub-batches) is well dealt with. We consider that the conclusion acquired by LOW, et al[4]with the number of sub-batches and the sizes of sub-batches fixed in advance for experiment (five instances were prepared in advance covering these two batch allocation methods) is not suitable for general situations.

    Optimum solutions to batch splitting for these four test problems through ALGRM1 are presented in Table 5, and the corresponding Gantt charts are shown in Figs. 7–10.From Table 5, we can see that the original batch of J1in P1 is split into 3, 3, 2 and 3 sub-batches for the four operations respectively, and the optimum batch sizes for the respective three sub-batches for the first operation are 0, 1 and 7,which means that the actual optimum batch number for the first operation of J1is 2. Sub-batches with size 0 are not displayed in Gantt charts.

    Table 5. Solutions to batch splitting for these four test problems through ALGRM1

    Fig. 7. Gantt chart for P1

    Fig. 8. Gantt chart for P2

    Fig. 9. Gantt chart for P3

    Fig. 10. Gantt chart for P4

    E1 in Gantt charts means machine 1, and E2 means machine 2, etc. Panes labeled with “s” in Gantt charts stand for set-up procedures, while those labeled with notations in“abc” format represent processing procedures, where “a”refers to a job index, “b” refers to an operation index, and“c” represents a sub-batch. Take Fig. 7 for example. The pane that labeled with “311” on machine 1 in Fig. 7 stands for the processing procedure for the first operation of the first sub-batch of J3, and the front pane labeled with “s”adjacent to it stands for the set-up procedure for the same operation. Combined with Table 5 and the time axis, we can get that the processing machine for the first operation of the first sub-batch of J3, with sub-batch size 5, is machine 1 after machine allocation, and the set-up procedure starts at time 0 and ends at time 5, and the processing procedure starts at time 5 and ends at time 30.As for the pane labeled with “213” on machine 5 in Fig. 7,there is no front pane labeled with “s” adjacent to it,meaning that the third sub-batch for the first operation of J2dose not need set-up procedure on machine 5, since the predecessor sub-batch in the processing sequence on that machine is of the same job and the same operation.

    4.2 Application of the proposed algorithm to the batch splitting scheduling problem in a speaker workshop

    To evaluate the performance of the proposed algorithm in a realistic problem, we adopt a batch splitting scheduling problem in a speaker workshop. The scheduling data is listed in Table 6. Set parameters the same as ALGRM1’s in section 4.1 and solve the problem through ALGRM1. We can obtain that BMN = 43 256, WMN = 48 151, No.BMN = 5 and AvT.CPU = 37.9 over 20 runs. The optimum solution to batch splitting for the realistic problem through ALGRM1 is presented in Table 7, and the corresponding Gantt charts are shown in Fig. 11. Since the set-up time consumed for a sub-batch is relatively short compared with the processing time of the whole sub-batch in this peoblem,set-up procedures are no longer illustrated with separate panes in Gantt chart. Panes labeled with “s” in Gantt chart stand for processing procedures together with set-up procedures.

    The results of all the five problems above confirm the validity of the model established in this paper for the variable-sized batch splitting scheduling problem in job shops, as well as the excellent performance of the proposed algorithm. From the data analysis for all test problems,there are several important findings. First, a schedule can be greatly improved through the variable-sized batch splitting technique. Second, the local search procedure and the adaptive crossover operator designed in this paper work effectively to gain a better performance, and our algorithm is capable of providing desirable solution within reasonable time limit. Third, variable-sized batch splitting performs better than equal-sized batch splitting in batch splitting scheduling problem with alternative machines.

    Table 6. Scheduling data in the batch splitting scheduling problem in a speaker workshop

    Table 7. Optimum solution to batch splitting for the realistic problem through ALGRM1

    Fig. 11. Gantt chart for the realistic problem

    5 Conclusions

    (1) A variable-sized batch splitting scheduling problem model with alternative machines, on the basis of predefined batch numbers of sub-batches for each operation per job, is established.

    (2) A new hybrid parallel algorithm is proposed to solve both the batch splitting problem and the batch scheduling problem, based on DE and genetic crossover operator. A problem-dependent local search procedure and an adaptive crossover operator are further designed for a better performance.

    (3) The experiments of batch splitting job shop scheduling are performed, and the results confirm the validity of the problem model and the excellent performance of the proposed algorithm.

    (4) Though the objective in this paper is to minimize the makespan, other objectives are also easily addressed by our approach.

    (5) The proposed algorithm could also be used to solve batch splitting scheduling problems with bounded batch sizes by adjusting Eq. (11) and Eq. (12) to get batch sizes within bounds.

    [1] MARTIN C H. A hybrid genetic algorithm/mathematical programming approach to the multi-family flowshop scheduling problem with lot streaming[J]. Omega, 2009, 37(1): 126–137.

    [2] PAN Quanke, ZHU Jianying. Optimization method for a job-shop scheduling problem with alternative machines in the batch process[J]. Chinese Journal of Mechanical Engineering, 2004,40(4): 36–39. (in Chinese)

    [3] SUN Zhijun, AN Jin, HUANG Weiqing. Lot scheduling with multiple process routes in job shop[J]. China Mechanical Engineering, 2008, 19(2): 183–187. (in Chinese)

    [4] LOW C, HSU C M, HUANG K I. Benefits of lot splitting in job-shop scheduling[J]. International Journal of Advanced Manufacturing Technology, 2004, 24(9–10): 773–780.

    [5] STORN R, PRICE K. Differential evolution—A simple and efficient heuristic for global optimization over continuous spaces[J].Journal of Global Optimization, 1997, 11(4): 341–359.

    [6] ONWUBOLU G, DAVENDRA D. Scheduling flow shops using differential evolution algorithm[J]. European Journal of Operational Research, 2006, 171(2): 674–692.

    [7] QIAN Bin, WANG Ling, HUANG Dexian, et al. An effective hybrid DE-based algorithm for multi-objective flow shop scheduling with limited buffers[J]. Computers & Operations Research, 2009, 36(1): 209–233.

    [8] NEARCHOU A C. A differential evolution approach for the common due date early/tardy job scheduling problem[J].Computers & Operations Research, 2008, 35(4): 1329–1343.

    [9] QIAN Bin, WANG Ling, HUANG Dexian et al. Scheduling multi-objective job shops using a memetic algorithm based on differential evolution[J]. International Journal of Advanced Manufacturing Technology, 2008, 35(9–10): 1 014–1 027.

    [10] WANG Chengdong, ZHANG Youyun. Adaptive pseudo-parallel genetic algorithm based on real coding[J]. Journal of Xi’an Jiaotong University, 2003, 37(7): 707–710. (in Chinese)

    [11] WANG Wanliang, WU Qidi. Intelligence algorithms of production scheduling and application[M]. Beijing: Science Press, 2007:52–57. (in Chinese)

    [12] AN Jin. The job shop scheduling problem with alternative machine in the batch process[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2005. (in Chinese)

    [13] LIN Nan, MENG Biao, FAN Yuqing. Hybrid genetic algorithm for multiple process and batch scheduling in job-shop[J]. Journal of Beijing University of Aeronautics and Astronautics, 2007, 33(12):1 471–1 476. (in Chinese)

    国产av国产精品国产| 日本欧美视频一区| 一区二区三区四区激情视频| 汤姆久久久久久久影院中文字幕| 国产又色又爽无遮挡免| 2021少妇久久久久久久久久久| 最近最新中文字幕免费大全7| 国产永久视频网站| 精品亚洲成国产av| 春色校园在线视频观看| 桃花免费在线播放| 欧美日本中文国产一区发布| 久久久久久久国产电影| 热re99久久国产66热| 国产激情久久老熟女| 亚洲国产精品一区二区三区在线| 亚洲久久久国产精品| 亚洲精华国产精华液的使用体验| 久久久久精品人妻al黑| 99国产综合亚洲精品| 精品熟女少妇av免费看| 寂寞人妻少妇视频99o| 久久鲁丝午夜福利片| 亚洲精华国产精华液的使用体验| 高清视频免费观看一区二区| 国产又色又爽无遮挡免| 国产在线一区二区三区精| 久久久久精品性色| 国产免费一区二区三区四区乱码| 春色校园在线视频观看| av国产精品久久久久影院| 国产 一区精品| 日本与韩国留学比较| 日产精品乱码卡一卡2卡三| 黄片无遮挡物在线观看| 丝袜人妻中文字幕| 最近最新中文字幕大全免费视频 | 国产 精品1| 国产精品久久久久久精品电影小说| 最近2019中文字幕mv第一页| 一边摸一边做爽爽视频免费| 午夜老司机福利剧场| av国产精品久久久久影院| 免费观看无遮挡的男女| 国产在视频线精品| 亚洲精品国产av成人精品| 午夜福利视频精品| 男女高潮啪啪啪动态图| √禁漫天堂资源中文www| 97在线视频观看| 久久精品国产自在天天线| 国产极品天堂在线| 欧美日韩综合久久久久久| 高清黄色对白视频在线免费看| 在线天堂最新版资源| 少妇高潮的动态图| 国产免费现黄频在线看| 国产深夜福利视频在线观看| 国产精品麻豆人妻色哟哟久久| 亚洲国产精品999| 男女无遮挡免费网站观看| videos熟女内射| 中文字幕免费在线视频6| 国产精品麻豆人妻色哟哟久久| 日韩,欧美,国产一区二区三区| 90打野战视频偷拍视频| 国产精品久久久久久久电影| 亚洲精品视频女| 亚洲av国产av综合av卡| 日韩制服骚丝袜av| 十分钟在线观看高清视频www| 22中文网久久字幕| 男人操女人黄网站| 亚洲国产av影院在线观看| 男人操女人黄网站| 国产福利在线免费观看视频| 久久人妻熟女aⅴ| 亚洲av日韩在线播放| 国产xxxxx性猛交| 欧美日韩亚洲高清精品| 日韩免费高清中文字幕av| 美女内射精品一级片tv| 亚洲欧洲精品一区二区精品久久久 | 欧美成人午夜精品| 91精品伊人久久大香线蕉| 最近中文字幕高清免费大全6| 午夜免费鲁丝| 亚洲 欧美一区二区三区| 美女xxoo啪啪120秒动态图| 久久综合国产亚洲精品| 有码 亚洲区| 各种免费的搞黄视频| av片东京热男人的天堂| 国产精品成人在线| 亚洲欧美精品自产自拍| 久久免费观看电影| 国产极品天堂在线| 一区二区三区精品91| 丝袜人妻中文字幕| 国产精品一国产av| 日韩不卡一区二区三区视频在线| a级毛片在线看网站| 欧美精品一区二区大全| 精品国产露脸久久av麻豆| 亚洲第一区二区三区不卡| 国产 一区精品| 久久精品国产自在天天线| 色婷婷av一区二区三区视频| 精品午夜福利在线看| 精品午夜福利在线看| 精品一区在线观看国产| 亚洲欧美日韩卡通动漫| 王馨瑶露胸无遮挡在线观看| 欧美 亚洲 国产 日韩一| 久久精品久久久久久久性| 国产又色又爽无遮挡免| 两个人免费观看高清视频| 赤兔流量卡办理| 亚洲欧美色中文字幕在线| 高清毛片免费看| 丝瓜视频免费看黄片| 久久精品国产a三级三级三级| 精品亚洲成a人片在线观看| 少妇精品久久久久久久| 巨乳人妻的诱惑在线观看| 日韩一区二区视频免费看| 国产又爽黄色视频| 日韩视频在线欧美| 免费看不卡的av| 久久鲁丝午夜福利片| 久久鲁丝午夜福利片| 久久女婷五月综合色啪小说| 国产免费现黄频在线看| 成人免费观看视频高清| 亚洲经典国产精华液单| 中文字幕人妻丝袜制服| 最近中文字幕2019免费版| 在线天堂最新版资源| 色网站视频免费| 欧美精品人与动牲交sv欧美| 国产成人精品久久久久久| 免费观看在线日韩| 大陆偷拍与自拍| 亚洲成人av在线免费| 大陆偷拍与自拍| 波野结衣二区三区在线| 黄色一级大片看看| 日韩,欧美,国产一区二区三区| 看免费成人av毛片| 国产高清不卡午夜福利| 你懂的网址亚洲精品在线观看| 国产女主播在线喷水免费视频网站| 中文天堂在线官网| 久久久亚洲精品成人影院| 日韩人妻精品一区2区三区| 国产淫语在线视频| 日本欧美视频一区| av黄色大香蕉| 青春草视频在线免费观看| 蜜桃在线观看..| 成年人免费黄色播放视频| 欧美日本中文国产一区发布| 久久女婷五月综合色啪小说| 国产有黄有色有爽视频| 在线看a的网站| 纵有疾风起免费观看全集完整版| 黑丝袜美女国产一区| 你懂的网址亚洲精品在线观看| 精品福利永久在线观看| 欧美精品一区二区免费开放| 波多野结衣一区麻豆| 22中文网久久字幕| 欧美亚洲 丝袜 人妻 在线| 香蕉丝袜av| 欧美精品人与动牲交sv欧美| 欧美日韩成人在线一区二区| 91aial.com中文字幕在线观看| 9热在线视频观看99| 免费久久久久久久精品成人欧美视频 | 国产成人精品福利久久| 国产在线免费精品| 老司机影院毛片| 黑丝袜美女国产一区| 交换朋友夫妻互换小说| 中文天堂在线官网| 亚洲激情五月婷婷啪啪| 五月伊人婷婷丁香| 亚洲av男天堂| 亚洲av福利一区| 国产精品欧美亚洲77777| 两个人看的免费小视频| 高清av免费在线| 视频中文字幕在线观看| 好男人视频免费观看在线| 最近2019中文字幕mv第一页| 老熟女久久久| 亚洲三级黄色毛片| 成人午夜精彩视频在线观看| 97超碰精品成人国产| 免费看光身美女| 五月开心婷婷网| 国产高清不卡午夜福利| 最近最新中文字幕大全免费视频 | 中国美白少妇内射xxxbb| 99国产精品免费福利视频| 日韩熟女老妇一区二区性免费视频| 全区人妻精品视频| 男人操女人黄网站| 91国产中文字幕| 男人操女人黄网站| 99热国产这里只有精品6| 一级毛片 在线播放| 亚洲内射少妇av| 大码成人一级视频| 国产高清国产精品国产三级| 国产精品久久久久久av不卡| 成年人午夜在线观看视频| 欧美3d第一页| 新久久久久国产一级毛片| 赤兔流量卡办理| 青春草视频在线免费观看| 欧美+日韩+精品| 欧美人与善性xxx| 国产高清不卡午夜福利| 22中文网久久字幕| 五月伊人婷婷丁香| 中文精品一卡2卡3卡4更新| 国产综合精华液| 亚洲国产最新在线播放| 五月天丁香电影| 三上悠亚av全集在线观看| 午夜福利视频在线观看免费| 国产精品人妻久久久久久| 欧美日本中文国产一区发布| 日本黄大片高清| 国产精品无大码| 亚洲综合色惰| 欧美另类一区| 亚洲高清免费不卡视频| 国产精品久久久久久精品电影小说| 妹子高潮喷水视频| 免费黄频网站在线观看国产| 国产成人午夜福利电影在线观看| 久久久久久久久久人人人人人人| 纵有疾风起免费观看全集完整版| 亚洲天堂av无毛| 最近最新中文字幕免费大全7| av天堂久久9| 国产成人精品婷婷| 少妇的逼好多水| 午夜激情久久久久久久| 激情视频va一区二区三区| 一二三四在线观看免费中文在 | av在线老鸭窝| 18禁国产床啪视频网站| 欧美日本中文国产一区发布| 国产精品国产三级专区第一集| 街头女战士在线观看网站| 久久久久久伊人网av| 嫩草影院入口| 妹子高潮喷水视频| 欧美97在线视频| 在线天堂中文资源库| 狠狠婷婷综合久久久久久88av| 亚洲精品,欧美精品| 国产一区亚洲一区在线观看| 观看美女的网站| 99久国产av精品国产电影| 亚洲国产成人一精品久久久| 国产精品国产av在线观看| 90打野战视频偷拍视频| 蜜臀久久99精品久久宅男| 各种免费的搞黄视频| 日本av手机在线免费观看| 国产精品99久久99久久久不卡 | 这个男人来自地球电影免费观看 | 亚洲国产看品久久| 十八禁网站网址无遮挡| 精品人妻偷拍中文字幕| 久久久国产一区二区| 日韩 亚洲 欧美在线| 日韩欧美一区视频在线观看| 成人手机av| 人妻人人澡人人爽人人| 两个人免费观看高清视频| 街头女战士在线观看网站| 日韩成人av中文字幕在线观看| 亚洲精品456在线播放app| 少妇高潮的动态图| 亚洲av.av天堂| www日本在线高清视频| 少妇的逼水好多| 2022亚洲国产成人精品| 亚洲情色 制服丝袜| 欧美丝袜亚洲另类| 一区二区日韩欧美中文字幕 | 国产精品三级大全| 婷婷成人精品国产| 人妻一区二区av| 汤姆久久久久久久影院中文字幕| 人人妻人人添人人爽欧美一区卜| 亚洲图色成人| 99视频精品全部免费 在线| 亚洲av福利一区| 曰老女人黄片| 一区二区日韩欧美中文字幕 | 免费av中文字幕在线| 人妻少妇偷人精品九色| 久久精品aⅴ一区二区三区四区 | 国产伦理片在线播放av一区| 日韩一本色道免费dvd| 欧美国产精品一级二级三级| a 毛片基地| 在线观看免费视频网站a站| 亚洲欧美精品自产自拍| 免费久久久久久久精品成人欧美视频 | 我要看黄色一级片免费的| 免费人成在线观看视频色| 日韩人妻精品一区2区三区| √禁漫天堂资源中文www| 日韩 亚洲 欧美在线| 日韩一区二区视频免费看| 美女大奶头黄色视频| 国产亚洲欧美精品永久| 咕卡用的链子| 国产亚洲av片在线观看秒播厂| 肉色欧美久久久久久久蜜桃| 菩萨蛮人人尽说江南好唐韦庄| 亚洲高清免费不卡视频| 欧美日韩亚洲高清精品| 国产成人精品福利久久| 精品久久久久久电影网| 久久午夜福利片| 少妇精品久久久久久久| 久久久久精品人妻al黑| 看非洲黑人一级黄片| 美女福利国产在线| 高清毛片免费看| 男的添女的下面高潮视频| 亚洲欧洲国产日韩| 久久青草综合色| 亚洲精品成人av观看孕妇| 国产淫语在线视频| 欧美日韩一区二区视频在线观看视频在线| 美女主播在线视频| 9色porny在线观看| 建设人人有责人人尽责人人享有的| 久久久欧美国产精品| 香蕉国产在线看| 综合色丁香网| 三上悠亚av全集在线观看| 精品人妻熟女毛片av久久网站| 色网站视频免费| 免费高清在线观看视频在线观看| 欧美日韩视频高清一区二区三区二| 久久精品久久久久久久性| 中国美白少妇内射xxxbb| 欧美亚洲 丝袜 人妻 在线| 国产精品一区二区在线不卡| 在线免费观看不下载黄p国产| 欧美变态另类bdsm刘玥| 1024视频免费在线观看| 国国产精品蜜臀av免费| 日韩 亚洲 欧美在线| 国产成人一区二区在线| 视频在线观看一区二区三区| 男女国产视频网站| 婷婷色av中文字幕| 精品酒店卫生间| 亚洲国产av影院在线观看| 下体分泌物呈黄色| 18+在线观看网站| 视频在线观看一区二区三区| 国产精品女同一区二区软件| 中文字幕制服av| 国产有黄有色有爽视频| 一级片'在线观看视频| 亚洲精品第二区| 看免费成人av毛片| 26uuu在线亚洲综合色| 性色avwww在线观看| 一级爰片在线观看| 国产成人精品久久久久久| 一边亲一边摸免费视频| 久久精品夜色国产| 大香蕉久久网| 18禁裸乳无遮挡动漫免费视频| 亚洲欧美中文字幕日韩二区| 日韩欧美一区视频在线观看| 国产黄色免费在线视频| 两个人看的免费小视频| 亚洲图色成人| 狠狠婷婷综合久久久久久88av| 大码成人一级视频| 日韩 亚洲 欧美在线| 一本一本久久a久久精品综合妖精 国产伦在线观看视频一区 | 国产精品一区www在线观看| 免费看不卡的av| 在线观看免费日韩欧美大片| 亚洲色图综合在线观看| 亚洲图色成人| 国产免费福利视频在线观看| 九色成人免费人妻av| 99热全是精品| 少妇高潮的动态图| 成人国产av品久久久| 黄色毛片三级朝国网站| 久久久久久人妻| 在线天堂最新版资源| 一边亲一边摸免费视频| 女人被躁到高潮嗷嗷叫费观| 天堂中文最新版在线下载| 在线观看美女被高潮喷水网站| 涩涩av久久男人的天堂| 亚洲精品久久久久久婷婷小说| 亚洲精品国产av成人精品| 亚洲久久久国产精品| 午夜激情久久久久久久| 亚洲av综合色区一区| 熟女电影av网| 免费大片18禁| 国产精品久久久av美女十八| 99香蕉大伊视频| 曰老女人黄片| 免费av不卡在线播放| 在线观看国产h片| 亚洲av在线观看美女高潮| 亚洲精品日韩在线中文字幕| 丝袜美足系列| 赤兔流量卡办理| 一级毛片 在线播放| 欧美3d第一页| 午夜福利在线观看免费完整高清在| 精品第一国产精品| 亚洲精品一区蜜桃| 大香蕉久久成人网| 好男人视频免费观看在线| 国产淫语在线视频| 免费在线观看黄色视频的| 国产老妇伦熟女老妇高清| 亚洲国产精品999| 七月丁香在线播放| 建设人人有责人人尽责人人享有的| 国产高清不卡午夜福利| 黑人猛操日本美女一级片| 国产一级毛片在线| 亚洲欧美精品自产自拍| 91精品国产国语对白视频| 久热这里只有精品99| 男的添女的下面高潮视频| 极品少妇高潮喷水抽搐| 国产精品 国内视频| 精品少妇内射三级| 午夜免费男女啪啪视频观看| 中文字幕人妻熟女乱码| av女优亚洲男人天堂| www.av在线官网国产| 一级片'在线观看视频| 午夜精品国产一区二区电影| 肉色欧美久久久久久久蜜桃| 校园人妻丝袜中文字幕| 一级爰片在线观看| 哪个播放器可以免费观看大片| 高清欧美精品videossex| 十八禁网站网址无遮挡| 九色成人免费人妻av| 日韩电影二区| 日韩av免费高清视频| 免费黄网站久久成人精品| 免费观看a级毛片全部| 亚洲国产成人一精品久久久| 又大又黄又爽视频免费| 如何舔出高潮| 69精品国产乱码久久久| 丰满饥渴人妻一区二区三| 欧美亚洲 丝袜 人妻 在线| 国产成人精品福利久久| 亚洲欧美日韩卡通动漫| 18禁国产床啪视频网站| 我的女老师完整版在线观看| 韩国高清视频一区二区三区| 免费高清在线观看视频在线观看| 少妇熟女欧美另类| 熟女电影av网| 91精品伊人久久大香线蕉| 大香蕉久久网| 国产av国产精品国产| 国产伦理片在线播放av一区| 日韩av免费高清视频| 新久久久久国产一级毛片| 免费观看a级毛片全部| 亚洲欧美一区二区三区国产| 永久网站在线| 9191精品国产免费久久| 国产欧美亚洲国产| 中国国产av一级| 巨乳人妻的诱惑在线观看| 精品一区二区三区四区五区乱码 | 欧美精品国产亚洲| 如何舔出高潮| 婷婷色麻豆天堂久久| 国产老妇伦熟女老妇高清| 久久久久久久久久人人人人人人| 黑人欧美特级aaaaaa片| 巨乳人妻的诱惑在线观看| 欧美bdsm另类| 51国产日韩欧美| 中文字幕人妻丝袜制服| 人人澡人人妻人| 久久这里有精品视频免费| 亚洲综合色惰| 久久久久久人人人人人| 亚洲av国产av综合av卡| 女性被躁到高潮视频| 国产男女超爽视频在线观看| 国产综合精华液| 亚洲欧美成人精品一区二区| 成人18禁高潮啪啪吃奶动态图| 精品人妻在线不人妻| 亚洲欧洲精品一区二区精品久久久 | 国产精品国产av在线观看| 国产视频首页在线观看| 久久久精品免费免费高清| 18禁裸乳无遮挡动漫免费视频| 久久久久久久亚洲中文字幕| 十分钟在线观看高清视频www| 高清在线视频一区二区三区| 久久精品国产自在天天线| 婷婷色av中文字幕| 久久免费观看电影| 日韩免费高清中文字幕av| 色94色欧美一区二区| 最后的刺客免费高清国语| 日本黄大片高清| 97人妻天天添夜夜摸| 天天操日日干夜夜撸| 国产精品99久久99久久久不卡 | 99热全是精品| 久久免费观看电影| 国产老妇伦熟女老妇高清| 全区人妻精品视频| 午夜老司机福利剧场| 捣出白浆h1v1| 国产成人免费无遮挡视频| videosex国产| 啦啦啦中文免费视频观看日本| 尾随美女入室| 亚洲精品国产色婷婷电影| 国产xxxxx性猛交| 成人国语在线视频| 国产精品蜜桃在线观看| 欧美日韩成人在线一区二区| 亚洲欧美日韩另类电影网站| 免费观看在线日韩| 美国免费a级毛片| 亚洲av电影在线进入| 免费观看性生交大片5| 亚洲,欧美精品.| 久久久国产一区二区| 久久国产精品男人的天堂亚洲 | 国产成人欧美| 18在线观看网站| 97精品久久久久久久久久精品| 人成视频在线观看免费观看| 国产片特级美女逼逼视频| 汤姆久久久久久久影院中文字幕| 欧美xxxx性猛交bbbb| 精品人妻偷拍中文字幕| 精品一区二区三区视频在线| 中文字幕另类日韩欧美亚洲嫩草| videossex国产| 国产精品久久久久久久电影| 9热在线视频观看99| 日韩av在线免费看完整版不卡| 国产精品国产三级国产专区5o| 婷婷色综合大香蕉| 免费黄网站久久成人精品| 极品人妻少妇av视频| 久久狼人影院| 视频中文字幕在线观看| 国产精品.久久久| 亚洲国产最新在线播放| 男女免费视频国产| 在线 av 中文字幕| 男女啪啪激烈高潮av片| 99热6这里只有精品| 男女边摸边吃奶| 三级国产精品片| 婷婷色麻豆天堂久久| 韩国av在线不卡| 丝袜人妻中文字幕| 国产精品久久久久久精品古装| 亚洲欧洲国产日韩| 亚洲国产精品国产精品| 日日撸夜夜添| 亚洲国产看品久久| 2018国产大陆天天弄谢| 一区二区日韩欧美中文字幕 | 亚洲av免费高清在线观看| 国产有黄有色有爽视频| 久久国内精品自在自线图片| 免费女性裸体啪啪无遮挡网站| 男人爽女人下面视频在线观看| 日本黄大片高清| 水蜜桃什么品种好| freevideosex欧美| 超碰97精品在线观看| 五月伊人婷婷丁香| 高清毛片免费看| av片东京热男人的天堂| 精品亚洲成a人片在线观看| 国产成人免费观看mmmm| av在线老鸭窝| 欧美精品国产亚洲| kizo精华|