Research On Batch Scheduling Processing On Parallel Machines With Two-stage Integrated Scheduling

Production scheduling problem has been widely used in modern life,it involves multiple fields in practice,such as processing factory production,steel casting,taobao,logistics,network communication,computer science and technology,etc.Classical scheduling problem in real life applications is limited,can not fully meet the needs of society,so the batch scheduling problem has been proposed,batch scheduling problem is no longer constrained by classical scheduling problem,but it is the extension of the classical scheduling problem.It breaks the shackles of a machine that can only process one job,implementing several jobs can be processed on a batch processing machine simultaneously.This not only improves the efficiency of production but also increases the utilization of resources.With the development of society,the batch scheduling problem with the same job size can not meet the actual needs of society.Therefore,the scheduling problem of different job sizes is studied and more complicated.However,the two-stage integrated scheduling problem studied in this paper involves not only the batch scheduling problem but also the product delivery problem,which is more complicated than any scheduling problem studied above.The batch scheduling problem of single machine has been proved to be an NP-hard problem by researchers[12].Therefore,the two-stage problem in this paper is a strong NP-hard problem.Studying this issue in depth is of great significance.This paper first briefly describes the research background,concepts and classification of scheduling problems,then a brief introduction to the batch scheduling problems and product delivery issues and describes the research status of batch scheduling problem,as well as the classical scheduling problem,the modern scheduling problem and the scheduling problem of the discrepancy size.Meanwhile,the research status of the product delivery problem is introduced.Secondly,it introduce the three mainstream batch scheduling algorithms:deterministic algorithm,heuristic algorithm and meta-heuristic algorithm respectively and introduced the characteristics of the algorithm,the framework of the algorithm and the description of the algorithm.Third,this paper studies the production distribution scheduling problem of two-stage parallel batch processing machine.In the production stage,the jobs are to be grouped into batches which are then scheduled on parallel batch processing machines.During the distribution phase,vehicles with the same capacity are dispatched and the processed batch is delivered to the customer.The objective of this paper is to minimize the total weighted delivery time of the jobs and and gives a lower bound algorithm to evaluate the proposed algorithm.To solve this NP-hard problem,a deterministic heuristic algorithm(H)and two hybrid meta-heuristic algorithms based on ant colony optimization(HACO,MMAS)are proposed respectively.Thirdly,by analyzing the nature of the problem,heuristic information and pheromones are defined,at the same time,combined with the local optimization strategy,the ant colony first constructs the scheduling.In addition,this paper designs a heuristic algorithm for the transportation of completed batches.Then,an example of the problem is generated randomly,and the performance of the proposed algorithm is compared with that of the proposed algorithm.At the same time,the experimental results are analyzed.The results show that the MMAS is slightly better than the HACO algorithm and a better solution than H can be found in a reasonable amount of time.Finally,this paper summarizes the two-stage integrated scheduling and the proposed problems under the condition of batch processor in this paper and makes a further prospect for the future research direction.