• <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)

    精品国内亚洲2022精品成人 | 国产精品熟女久久久久浪| 极品人妻少妇av视频| 母亲3免费完整高清在线观看| 五月开心婷婷网| 蜜桃在线观看..| 国产xxxxx性猛交| 国产又爽黄色视频| 欧美97在线视频| 亚洲少妇的诱惑av| 纯流量卡能插随身wifi吗| 一边摸一边做爽爽视频免费| 欧美一级毛片孕妇| 国产极品粉嫩免费观看在线| av网站免费在线观看视频| 欧美日韩成人在线一区二区| 欧美激情高清一区二区三区| 日韩欧美一区二区三区在线观看 | 少妇裸体淫交视频免费看高清 | 黄片播放在线免费| 国产亚洲午夜精品一区二区久久| 中文字幕色久视频| 两人在一起打扑克的视频| 午夜老司机福利片| 成人黄色视频免费在线看| 欧美精品一区二区免费开放| 男人操女人黄网站| 亚洲一卡2卡3卡4卡5卡精品中文| av福利片在线| 国产av又大| 黄片大片在线免费观看| 亚洲精品日韩在线中文字幕| 男女下面插进去视频免费观看| 国产免费福利视频在线观看| 精品免费久久久久久久清纯 | 精品卡一卡二卡四卡免费| 欧美另类亚洲清纯唯美| 成人国语在线视频| e午夜精品久久久久久久| 亚洲精品乱久久久久久| 亚洲av男天堂| 精品一区二区三区四区五区乱码| 久久精品久久久久久噜噜老黄| 成人国产av品久久久| 又大又爽又粗| 亚洲一区二区三区欧美精品| 亚洲黑人精品在线| 丝袜美腿诱惑在线| 香蕉丝袜av| 成在线人永久免费视频| 十八禁网站网址无遮挡| 国产亚洲欧美在线一区二区| 亚洲av电影在线进入| 日本a在线网址| 在线看a的网站| 汤姆久久久久久久影院中文字幕| 18在线观看网站| tocl精华| 99香蕉大伊视频| 热99re8久久精品国产| 极品人妻少妇av视频| e午夜精品久久久久久久| 中文精品一卡2卡3卡4更新| 熟女少妇亚洲综合色aaa.| 午夜久久久在线观看| 亚洲精品国产色婷婷电影| 18禁国产床啪视频网站| 人人妻,人人澡人人爽秒播| tube8黄色片| 欧美午夜高清在线| www.999成人在线观看| 亚洲精品美女久久久久99蜜臀| 亚洲av电影在线进入| 日本a在线网址| 在线观看免费日韩欧美大片| 成人黄色视频免费在线看| 国产国语露脸激情在线看| 性少妇av在线| 国产亚洲欧美精品永久| 黑人猛操日本美女一级片| 成人18禁高潮啪啪吃奶动态图| 50天的宝宝边吃奶边哭怎么回事| 真人做人爱边吃奶动态| 日韩免费高清中文字幕av| 老司机影院成人| 久热爱精品视频在线9| 老汉色∧v一级毛片| 亚洲av成人不卡在线观看播放网 | 欧美日韩一级在线毛片| 久久久久久亚洲精品国产蜜桃av| 欧美国产精品一级二级三级| 天堂8中文在线网| 热re99久久国产66热| 欧美性长视频在线观看| 一二三四在线观看免费中文在| 欧美日韩黄片免| 婷婷丁香在线五月| 国产成人欧美在线观看 | 男人添女人高潮全过程视频| 免费黄频网站在线观看国产| 国产日韩欧美在线精品| 国产真人三级小视频在线观看| 亚洲中文字幕日韩| 亚洲熟女毛片儿| 丝袜在线中文字幕| 国产亚洲精品第一综合不卡| 成人亚洲精品一区在线观看| tocl精华| 十分钟在线观看高清视频www| 欧美精品av麻豆av| 一级毛片精品| 在线观看舔阴道视频| 国产精品熟女久久久久浪| a 毛片基地| 亚洲国产成人一精品久久久| 久久人人97超碰香蕉20202| 精品人妻在线不人妻| 国产伦理片在线播放av一区| 精品人妻熟女毛片av久久网站| 性高湖久久久久久久久免费观看| 90打野战视频偷拍视频| 欧美xxⅹ黑人| 这个男人来自地球电影免费观看| 18禁黄网站禁片午夜丰满| 精品欧美一区二区三区在线| 正在播放国产对白刺激| 日日摸夜夜添夜夜添小说| 精品高清国产在线一区| 欧美日韩精品网址| 黄网站色视频无遮挡免费观看| 久久久久久久国产电影| 亚洲第一av免费看| 欧美午夜高清在线| 久久女婷五月综合色啪小说| 中文字幕人妻丝袜制服| 91av网站免费观看| 亚洲国产精品一区二区三区在线| 午夜福利在线观看吧| 美女主播在线视频| 最新在线观看一区二区三区| 成人影院久久| 亚洲 欧美一区二区三区| 丰满少妇做爰视频| 亚洲欧美激情在线| 99久久人妻综合| 午夜福利一区二区在线看| 女性生殖器流出的白浆| 高清黄色对白视频在线免费看| 久久久国产成人免费| 各种免费的搞黄视频| 精品第一国产精品| 黄片播放在线免费| 夜夜骑夜夜射夜夜干| 亚洲五月色婷婷综合| 久久人人97超碰香蕉20202| 亚洲一码二码三码区别大吗| 97精品久久久久久久久久精品| 国产亚洲精品久久久久5区| 在线观看免费高清a一片| 另类亚洲欧美激情| 久久久国产一区二区| 18在线观看网站| 18禁黄网站禁片午夜丰满| 亚洲国产精品一区三区| 久久午夜综合久久蜜桃| 在线观看舔阴道视频| 少妇 在线观看| 国产亚洲精品第一综合不卡| 在线精品无人区一区二区三| cao死你这个sao货| 午夜老司机福利片| 黄片播放在线免费| 亚洲国产精品成人久久小说| 女人被躁到高潮嗷嗷叫费观| 在线观看免费视频网站a站| 国产在线视频一区二区| 国产精品 国内视频| 午夜老司机福利片| 青青草视频在线视频观看| 色老头精品视频在线观看| 在线亚洲精品国产二区图片欧美| 另类亚洲欧美激情| 狠狠狠狠99中文字幕| 最黄视频免费看| 国产亚洲欧美精品永久| 午夜91福利影院| 亚洲国产成人一精品久久久| 精品一品国产午夜福利视频| 日韩视频一区二区在线观看| 国产精品成人在线| 亚洲综合色网址| 啦啦啦在线免费观看视频4| 国产日韩欧美视频二区| 搡老岳熟女国产| 色94色欧美一区二区| 后天国语完整版免费观看| 2018国产大陆天天弄谢| 9191精品国产免费久久| 热re99久久精品国产66热6| 国产在线观看jvid| 亚洲精品粉嫩美女一区| 一级,二级,三级黄色视频| 久久久久视频综合| 99国产精品99久久久久| 日韩中文字幕欧美一区二区| 男人添女人高潮全过程视频| 性高湖久久久久久久久免费观看| 免费高清在线观看视频在线观看| 亚洲成国产人片在线观看| 久久 成人 亚洲| 侵犯人妻中文字幕一二三四区| 亚洲伊人色综图| 老汉色av国产亚洲站长工具| 亚洲一区二区三区欧美精品| 操美女的视频在线观看| svipshipincom国产片| 日韩免费高清中文字幕av| 中文字幕制服av| 亚洲男人天堂网一区| 美女大奶头黄色视频| 久久久久久亚洲精品国产蜜桃av| 精品国内亚洲2022精品成人 | 三上悠亚av全集在线观看| 国产高清视频在线播放一区 | 高清av免费在线| 精品少妇内射三级| 国产一级毛片在线| 人人妻人人爽人人添夜夜欢视频| 又大又爽又粗| 久久久久久亚洲精品国产蜜桃av| 精品国产乱子伦一区二区三区 | 亚洲七黄色美女视频| 精品一区二区三区四区五区乱码| 青青草视频在线视频观看| 日韩 亚洲 欧美在线| 久久久国产欧美日韩av| 91成年电影在线观看| 一级,二级,三级黄色视频| 18禁黄网站禁片午夜丰满| 丰满少妇做爰视频| 久久99热这里只频精品6学生| 中文字幕另类日韩欧美亚洲嫩草| 69精品国产乱码久久久| 50天的宝宝边吃奶边哭怎么回事| 一边摸一边做爽爽视频免费| 国产真人三级小视频在线观看| 精品国产一区二区三区久久久樱花| 国产熟女午夜一区二区三区| 国产成人啪精品午夜网站| 一本综合久久免费| 国产欧美日韩一区二区三区在线| 国产又色又爽无遮挡免| 天天操日日干夜夜撸| 亚洲成国产人片在线观看| a 毛片基地| 丝袜脚勾引网站| 亚洲成人免费电影在线观看| 国产深夜福利视频在线观看| 国产三级黄色录像| 成年人黄色毛片网站| 搡老乐熟女国产| 一级黄色大片毛片| 成年动漫av网址| 精品国产一区二区三区久久久樱花| 日韩有码中文字幕| 国产日韩一区二区三区精品不卡| 一边摸一边抽搐一进一出视频| 国产亚洲精品第一综合不卡| 久久久久精品人妻al黑| 黄片大片在线免费观看| 欧美另类一区| 又黄又粗又硬又大视频| 欧美+亚洲+日韩+国产| 99re6热这里在线精品视频| 欧美成狂野欧美在线观看| 成人18禁高潮啪啪吃奶动态图| 欧美成人午夜精品| 1024香蕉在线观看| 中国美女看黄片| 久久久久久亚洲精品国产蜜桃av| av电影中文网址| 成人国产一区最新在线观看| 国产在线免费精品| 18禁黄网站禁片午夜丰满| 久久99热这里只频精品6学生| 无限看片的www在线观看| 亚洲三区欧美一区| 日韩电影二区| 永久免费av网站大全| 大片电影免费在线观看免费| 日韩免费高清中文字幕av| 国产成+人综合+亚洲专区| 免费在线观看影片大全网站| 99国产精品免费福利视频| 69精品国产乱码久久久| av国产精品久久久久影院| 12—13女人毛片做爰片一| 国产欧美亚洲国产| 操出白浆在线播放| 午夜日韩欧美国产| 自线自在国产av| 国产精品.久久久| 菩萨蛮人人尽说江南好唐韦庄| 亚洲中文日韩欧美视频| 久久久久久久国产电影| 性高湖久久久久久久久免费观看| 美女主播在线视频| 一级毛片女人18水好多| 老汉色∧v一级毛片| 黄色视频不卡| 菩萨蛮人人尽说江南好唐韦庄| 91九色精品人成在线观看| 极品少妇高潮喷水抽搐| 91av网站免费观看| 成人三级做爰电影| 水蜜桃什么品种好| 他把我摸到了高潮在线观看 | 久久毛片免费看一区二区三区| 亚洲国产日韩一区二区| 美女脱内裤让男人舔精品视频| 中国美女看黄片| 欧美精品一区二区免费开放| 夜夜夜夜夜久久久久| 欧美国产精品一级二级三级| 搡老乐熟女国产| 亚洲 欧美一区二区三区| 午夜福利在线观看吧| 精品国产一区二区久久| 成人国语在线视频| 免费久久久久久久精品成人欧美视频| 中国国产av一级| 人人澡人人妻人| 亚洲专区字幕在线| 亚洲中文字幕日韩| 免费黄频网站在线观看国产| 日韩欧美一区二区三区在线观看 | 精品一区二区三区av网在线观看 | 狠狠狠狠99中文字幕| 中文精品一卡2卡3卡4更新| 欧美精品亚洲一区二区| 国产91精品成人一区二区三区 | 久9热在线精品视频| 在线观看免费高清a一片| av在线app专区| 国产有黄有色有爽视频| 欧美日韩亚洲国产一区二区在线观看 | 久久久久久久久久久久大奶| 精品一区在线观看国产| 韩国高清视频一区二区三区| 在线天堂中文资源库| 一区二区av电影网| 色播在线永久视频| 丁香六月天网| 99国产精品一区二区蜜桃av | 日韩 欧美 亚洲 中文字幕| 美女高潮喷水抽搐中文字幕| 午夜91福利影院| 亚洲av电影在线进入| 国产亚洲av高清不卡| 日韩欧美一区视频在线观看| 99精品久久久久人妻精品| 99九九在线精品视频| 欧美精品高潮呻吟av久久| 性色av乱码一区二区三区2| 成人黄色视频免费在线看| 欧美精品av麻豆av| 久久久久久久大尺度免费视频| 最近中文字幕2019免费版| 黑人欧美特级aaaaaa片| 人人妻,人人澡人人爽秒播| 视频在线观看一区二区三区| 国产精品一区二区免费欧美 | av欧美777| 男人操女人黄网站| 久久精品国产综合久久久| 午夜影院在线不卡| 麻豆av在线久日| 久久国产精品人妻蜜桃| 欧美日韩亚洲高清精品| 亚洲性夜色夜夜综合| 男女国产视频网站| 国产一级毛片在线| 国产有黄有色有爽视频| 一级毛片电影观看| 久久久久久久大尺度免费视频| 日本a在线网址| 精品国产一区二区久久| 99九九在线精品视频| 国产xxxxx性猛交| 国产精品成人在线| 真人做人爱边吃奶动态| 国产精品久久久av美女十八| 嫁个100分男人电影在线观看| 亚洲色图综合在线观看| 99久久人妻综合| cao死你这个sao货| 精品国产乱子伦一区二区三区 | 视频区图区小说| 久久精品亚洲熟妇少妇任你| 亚洲视频免费观看视频| 久久久精品国产亚洲av高清涩受| 亚洲一区中文字幕在线| 日本精品一区二区三区蜜桃| 国产成人av教育| 青青草视频在线视频观看| 国产亚洲精品一区二区www | 婷婷丁香在线五月| 激情视频va一区二区三区| 人人妻人人澡人人爽人人夜夜| 老司机福利观看| 亚洲全国av大片| 久久中文字幕一级| www.熟女人妻精品国产| 自线自在国产av| av超薄肉色丝袜交足视频| 亚洲色图综合在线观看| 在线观看一区二区三区激情| 国产精品偷伦视频观看了| 我要看黄色一级片免费的| 亚洲国产精品999| 可以免费在线观看a视频的电影网站| 亚洲精品在线美女| 性色av乱码一区二区三区2| 9色porny在线观看| 在线观看一区二区三区激情| 亚洲天堂av无毛| 亚洲午夜精品一区,二区,三区| 99精品欧美一区二区三区四区| 老司机午夜福利在线观看视频 | 777久久人妻少妇嫩草av网站| 大香蕉久久网| 国产精品欧美亚洲77777| 成人国产一区最新在线观看| 18在线观看网站| 亚洲欧美清纯卡通| 日韩,欧美,国产一区二区三区| √禁漫天堂资源中文www| 亚洲 国产 在线| 中亚洲国语对白在线视频| 日韩免费高清中文字幕av| 91精品三级在线观看| svipshipincom国产片| 99久久人妻综合| 深夜精品福利| 久久香蕉激情| 亚洲精品一卡2卡三卡4卡5卡 | 一本大道久久a久久精品| 免费高清在线观看日韩| 大码成人一级视频| 老司机靠b影院| 搡老岳熟女国产| 后天国语完整版免费观看| 午夜福利视频精品| 大片免费播放器 马上看| 精品国产一区二区三区四区第35| 99热国产这里只有精品6| 亚洲精品国产区一区二| 国内毛片毛片毛片毛片毛片| 亚洲欧洲精品一区二区精品久久久| 久久久久久久国产电影| 老鸭窝网址在线观看| 99九九在线精品视频| 欧美午夜高清在线| 少妇人妻久久综合中文| 建设人人有责人人尽责人人享有的| 黄色视频,在线免费观看| av网站在线播放免费| 日韩欧美国产一区二区入口| 久久久久久久久久久久大奶| 免费一级毛片在线播放高清视频 | av一本久久久久| av天堂在线播放| 大香蕉久久成人网| 欧美人与性动交α欧美软件| 亚洲国产日韩一区二区| www.熟女人妻精品国产| 97在线人人人人妻| tocl精华| 91精品伊人久久大香线蕉| 国产精品国产av在线观看| 亚洲av男天堂| 999精品在线视频| 亚洲激情五月婷婷啪啪| 亚洲av片天天在线观看| 亚洲久久久国产精品| 大片电影免费在线观看免费| 在线亚洲精品国产二区图片欧美| 亚洲一码二码三码区别大吗| 丝袜美足系列| 国产91精品成人一区二区三区 | 大码成人一级视频| 日韩大片免费观看网站| 婷婷成人精品国产| 69av精品久久久久久 | 热re99久久国产66热| 精品少妇黑人巨大在线播放| 成人三级做爰电影| 日韩欧美国产一区二区入口| 久9热在线精品视频| 国产精品免费视频内射| 在线看a的网站| 高清欧美精品videossex| 欧美日韩亚洲综合一区二区三区_| 亚洲精品久久午夜乱码| 考比视频在线观看| 爱豆传媒免费全集在线观看| 999久久久国产精品视频| 中国美女看黄片| 五月天丁香电影| 成人亚洲精品一区在线观看| 淫妇啪啪啪对白视频 | 五月开心婷婷网| 亚洲精品久久午夜乱码| 国产主播在线观看一区二区| 亚洲欧美成人综合另类久久久| 不卡一级毛片| 亚洲一码二码三码区别大吗| 亚洲欧美清纯卡通| 90打野战视频偷拍视频| 久久久久精品国产欧美久久久 | 久久国产精品大桥未久av| av在线播放精品| kizo精华| 熟女少妇亚洲综合色aaa.| 一个人免费看片子| 极品人妻少妇av视频| 欧美 日韩 精品 国产| 91国产中文字幕| 999久久久精品免费观看国产| 久久久久精品人妻al黑| 欧美日韩视频精品一区| 国产高清国产精品国产三级| 9热在线视频观看99| 午夜影院在线不卡| 99精国产麻豆久久婷婷| 交换朋友夫妻互换小说| 国产欧美日韩综合在线一区二区| 777米奇影视久久| 精品国产乱子伦一区二区三区 | 成年av动漫网址| 成人手机av| 亚洲国产欧美日韩在线播放| 1024视频免费在线观看| 岛国在线观看网站| 精品国产乱码久久久久久男人| 午夜日韩欧美国产| 久久女婷五月综合色啪小说| 国产成人a∨麻豆精品| 国产亚洲欧美在线一区二区| 看免费av毛片| 日韩三级视频一区二区三区| 久久久久久久久免费视频了| 国产免费av片在线观看野外av| 丰满人妻熟妇乱又伦精品不卡| 少妇被粗大的猛进出69影院| www.熟女人妻精品国产| 在线观看免费视频网站a站| 色综合欧美亚洲国产小说| 亚洲第一av免费看| 亚洲国产欧美在线一区| 久久国产精品男人的天堂亚洲| 成年女人毛片免费观看观看9 | 超色免费av| 亚洲精品国产区一区二| 天堂俺去俺来也www色官网| 999久久久精品免费观看国产| 大香蕉久久成人网| 少妇 在线观看| 欧美成狂野欧美在线观看| 亚洲国产欧美日韩在线播放| 日本一区二区免费在线视频| 欧美+亚洲+日韩+国产| 老司机午夜十八禁免费视频| 国产日韩欧美亚洲二区| 爱豆传媒免费全集在线观看| 午夜福利乱码中文字幕| 久久热在线av| 亚洲成人国产一区在线观看| 久久影院123| 美女高潮喷水抽搐中文字幕| 精品少妇久久久久久888优播| 啦啦啦 在线观看视频| 亚洲成人手机| 亚洲九九香蕉| 老司机亚洲免费影院| 一级,二级,三级黄色视频| 狂野欧美激情性bbbbbb| 久久性视频一级片| 91字幕亚洲| 夜夜夜夜夜久久久久| 日韩 欧美 亚洲 中文字幕| 国产亚洲午夜精品一区二区久久| 午夜福利一区二区在线看| 久久午夜综合久久蜜桃| 日本黄色日本黄色录像| 丁香六月欧美| 国产精品av久久久久免费| 亚洲欧美清纯卡通| 国内毛片毛片毛片毛片毛片| 成年人午夜在线观看视频| 久久天躁狠狠躁夜夜2o2o| 黄网站色视频无遮挡免费观看| 桃红色精品国产亚洲av| 亚洲精品国产av蜜桃| 夜夜夜夜夜久久久久| 日韩视频在线欧美| 亚洲精品国产色婷婷电影| 十八禁网站免费在线| 精品高清国产在线一区| 性色av乱码一区二区三区2| 亚洲欧美精品综合一区二区三区| 久久九九热精品免费| 亚洲全国av大片| 国产97色在线日韩免费| 日韩精品免费视频一区二区三区|