Research On Two-machine Flow Shop Scheduling Problems With Transportation Time

Flow shop scheduling problem is one of the classical problems in combinatorial optimiza-tion field.Because it is closely related to actual producing,it is widely studied at present.In the whole production process,the handling and transporting products are two principle factors.If combined,they can not only save the production costs,but also improve efficiency of pro-duction as well.This thesis focuses on the study of two-machine flow shop scheduling problems with transportation time.The goal is to minimize the total completion time.The computational complexity of the problems is first analyzed and the optimal algorithms are then designed for some special cases,and also the approximate algorithms are provided for the NP-hard problems finally.Firstly,for Model 1 in the flow shop environment,after jobs are processed on two machines,the conveyor transports jobs to the destination with most c jobs at a time,which has been proved to be ordinarily NP-hard when c=2 in 2007 by Yuan et al.Up to now,whether it is strongly NP-hard is still unsolved for many years.It is proved that the case is strongly NP-hard and close the open question.For Model 2 which is similar to the above model,the conveyor exists between two machines.In other words,jobs need to be transported from the first machine to the second machine for further processing.For this model,when the capacity of the conveyor is 1 or not less than 3,it has been proved to be strong NP-hard by Hurink and Lee et al respectively in 2001,but when the capacity is exactly 2,the complexity of the problem which is open for many years will turn out to be strongly NP-hard in this thesis.Secondly,if the conveyor is behind two machines,the scheduling scheme for three special cases are put forward when the capacity of conveyor is constant:(1)there is a linear time optimal algorithm for conveyor when the processing order of the two machines is given;(2)there is an optimal algorithm when the processing time of different jobs on the second machine is equal.The time complexity of the optimal algorithm should be O(n log n);(3)when the shortest processing time on the second machine is larger than or equal to the longest processing time on the first machine,there should be an optimal algorithm and the time complexity is O(n2),where n is the number of input jobs.Finally,when the capacity of conveyor is constant,by discussing the relationship between the two models and the specific three-machine flow shop problem,the approximation ratio from 2 is updated to 1+?,so polynomial approximation schemes for the two scheduling models will be provided eventually.