Research Of Scheduling Problems With Transportation Time

The traditional scheduling problem usually only considers the optimization of the machine processing stage.With the rapid development of industrial production,the makespan of jobs in real production needs to consider both processing and transportation.Therefore,the coordination and efficient treatment of the two stages is significant for enterprises to save costs,improve energy efficiency and increase profits.This paper mainly studies 4 important scheduling models with transportation time,including two parallel machines with a single destination model,a single machine with two types of destination model,a transporter in the middle of the flow-shop model,and a single machine with a single-destination model.For the first three models,which are known to be NP-hard problems,relevant approximate algorithms are designed,and the previous results are improved.For the last model,the optimal online algorithm is given.The main innovations are as follows:(1)The model of processing jobs in two parallel machines and then transporting to a single destination is studied.Each job has its size.There is a transporter with limited capacity in the model.The goal is to minimize the time that transporter finishes delivering all jobs and returns to the machine.Chang and Lee first proposed the model and gave a 2-approximation algorithm.Liu et al.And Zhang et al.gave(14/9+ε)-approximation algorithms.This paper presents a(3/2+ε)-approximation algorithm.When εis close to 0,the algorithm is tight.(2)The model of processing jobs on a single machine and then transporting to two types of destinations are studied.Each job has its destination in addition to its size.The goal is to minimize the time that transporter finishes delivering all j obs and returns to the machine.Chang and Lee first proposed the model and gave a 2-approximation algorithm.We analyze the advantages and disadvantages of the existing 2-approximation algorithm and improve the batching algorithm of the j ob so that the ratio of the transportation time of the algorithm in this paper to the transportation time required for optimal scheduling is reduced from 7/4of the previous algorithm to 3/2+ε.Finally,it is proved that the approximate ratio of the new algorithm is(11/6+ε).(3)The model of transporting the jobs processed on the first flow machine to the second machine for further processing is studied.The objective is to minimize the makespan.For this model,Gong and Tang first give a 7/3-approximation algorithm.Dong et al.Pointed out that the lower bound of the problem is 5/3.This paper analyzes the similarities and differences between this problem and the classical three flow-shop scheduling problem.Using the(1+ε)algorithm of the classical three flow-shop scheduling problem proposed by hall,a polynomialtime algorithm with an approximate ratio of(5/3+ε)is given.When εis close to 0,the algorithm is tight.(4)The online model of processing j obs on a single machine and then transporting them to a single destination is studied.The goal is to minimize the time that transporter finishes delivering all jobs and returns to the machine.The first online algorithm is given when jobs are agreeable,and the competition ratio of the algorithm is proved to be(?).Finally,the online algorithm is proved to be optimal by constructing an online sequence.This paper studies several machine scheduling models with transportation,expands the research results of the machine scheduling problems,and has guiding significance for industrial production to some extent.