Algorithm Research Of Batch Transportation And Logistics Scheduling

The scheduling problem of which the focus is on the optimal allocation of scare resources is an important branch in the field of combinatorial optimization.The job scheduling is essentially to solve how to distribute the limited resources to different tasks and to minimize the expected target according to the time order.The scheduling problem is widely used in real life,e.g.,the batch scheduling problem in the process of mechanical manufacturing,processing and transport in the supply chain management coordination,energy saving in internet area,the flow process in production line and flight scheduling,etc.Due to the limitation of resources of production and transport,how to arrange the processing order and how to transport increasingly attract the attention of researchers.In this study,the problems of two-stage batch scheduling with batch transportation,three machine scheduling,batch scheduling and logistics scheduling were studied respectively.With respect to these three problems,we proposed effective algorithms and analyzed their the effectiveness,respectively.The details of the article are given bellow:First of all,the research background and research significance of this topic are introduced in this article.The research development of scheduling theory,also the research status and detailed arrangement of this study reviews are illustrated.Brief descriptions of the scheduling theory,the arithmetic and the computational complexity,as well as some preliminary knowledge were given,which makes basic preparations for the following study of this thesis.Secondly,the two-phase flow process batch scheduling problem was study.Artifacts in different sizes firstly are processed in batch on the first machine,unfinished artifacts is passed to the second machine for processing by a single carrier.The capacity of carrier is c,which means that the total size of the workpiece in one transportation batch can not exceed the capacity of the carrier.The goal of this study is how to choose the processing order of to minimize the maximum completion time.Regarding to the two-phase flow process with batch scheduling problem,we designed a heuristic algorithm and analyzed its worst performance ratio.The effectiveness of the algorithm was verified using numerical examples.Thirdly,a scheduling problem of three machines flow process with transportation was considered.All artifacts must be processed on the first machine,M1,and then passed to machine M2 by a transport vehicles,and finally passed to the third machine for final processing.The goal of the problem is to find n a job processing and transportation solutions to minimize the makespan.Given a NP-hard problem,we established models for several cases,gave the approximate algorithm,and analyzed its worst performance ratio.Fourthly,the logistics scheduling problem of workpieces processing and producing until delivering to customers were studied.The problem is divided into two stages: the first stage is the processing stage.The workpieces with different weights are processed in batches on one machine.The second stage is the transport.The finished workpiece can be delivered to different specified destinations in batch through various transportations.Our goal is to minimize the sum of weighted completion time and transportation cost.A comprehensive description of complexity of several special cases was made in this study,and the algorithm of polynomial solvable case was proposed.Meanwhile,the approximation algorithm for the general case was provided,and the performance of the algorithm complexity was as well analyzed.