Study On Optimization Of Parallel-batching Scheduling With Release Times

Scheduling problems get used to model many applications in practice,such as manufacture,medical field,aerospace,transportation and other aspects,two management models are compiled according to parallel-batching and release times characteristics of production tasks.Firstly,this dissertation investigates the problem of scheduling step-deteriorating jobs with release times on a single parallel-batching machine.The processing time of each job can be represented as a simple non-linear step function of its starting time.The machine can process up to c jobs simultaneously as a batch.The objective is to minimize the makespan,and we show that the problem is strongly NP-hard.Then,a hybrid meta-heuristic algorithm BRKGA-VNS combining biased random-key genetic algorithm(BRKGA)and variable neighborhood search(VNS)is proposed to solve this problem.A heuristic algorithm H is developed based on the structural properties of the problem,and it is applied in the decoding procedure of the proposed algorithm.A series of computational experiments are conducted and the results show that the proposed hybrid algorithm can yield better solutions compared with BRKGA,PSO(Particle Swarm Optimization),and VNS.Secondly,this dissertation as well as investigates a scheduling problem based on uniform parallel machines,where the jobs with non-identical sizes and basic processing time.The processing speed of the processing machine is different,and because the jobs are delivered to the machines located different places for processing,the release times of different jobs are different.The objective of this problem is aimed at minimizing the completion time of the task.In this section,the jobs are grouped into batches by BFF-LPT heuristic,and then we present a hybrid TS-DE algorithm by which the formed batches are allocated onto the machines.At last,we evaluate the performance of algorithms which consist of TS-DE,TS and DE through computational experiments.Finally,we summed up the research content of this dissertation,and some suggestions on scheduling for future research are given.