Research On Batch Scheduling Processing On Parallel Machines With Energy Consumption

As a type of complex combinatorial optimization problems,production scheduling involves multiple fields in practice,such as the foundry industry,metal processing industry,logistics,communication,and so on.The main purpose of the research on production scheduling problem is to allocate the resources reasonably to improve the utilization and production efficiency.Additionally,sound schedule is able to raise the competitiveness of the enterprises greatly.With the development of the society,the problems of production scheduling have become more and more complicated,from the classical scheduling problem to the batch scheduling problem.The scheduling on batch processing machines(the batch scheduling problem)differs from the traditional scheduling problems mainly in that several jobs can be processed on a batch processing machine simultaneously.The processing time of a batch,consisting of several jobs,equals to the longest processing time of all jobs in the batch.The complexity of batch scheduling is decided by the constraints of the jobs,the machines and the objective functions.In fact,many of the batch scheduling problems,even those with one single machine have been proved to be NP-hard.So the researchers have already concentrated on feasible and efficient algorithms.Firstly,the background of production scheduling problem is presented in this thesis.Then,the research status of the batch scheduling on single machine,multiple machines,the constraint with dynamic job arrivals,and the objective related to the energy consumption is surveyed.Secondly,this paper introduces the prevalent approaches for batch scheduling,including the deterministic methods,the heuristics and the meta-heuristic algorithms.Specifically,the characteristics,schemes,and the descriptions of the three types of algorithms are discussed.Thirdly,the problem with dynamic job arrivals of minimizing the makespan and the total electric power cost simultaneously on parallel batch processing machines is discussed.With the mathematic model constructed,a Pareto-based ant colony optimization(PACO)algorithm is proposed.Depending on whether the current batch being delayed after the job is added into,two candidate lists are constructed to narrow the search space.Moreover,heuristic information is designed for each candidate list.In addition,the objective-oriented local optimization methods are applied to improve the solution quality.Finally,a description and the flow chart of the PACO algorithm are shown.Fourthly,to verify the validity of the proposed algorithm,the proposed algorithm is compared with existing three multi-objective algorithms through extensive simulation experiments by seven evaluated metrics.Through experimental results,we can see that the proposed algorithm outperforms all of the other three compared algorithms,especially on large-scale instances.To compare the solution quality of the four algorithms clearly,the solution distributions of some instances are illustrated.Finally,this paper summarizes batching scheduling problem studied in this paper,as well as the provided approaches according to the simulation experimental results.A brief introduction of further research based on this paper is presented.