Optimal Algorithms For Hybrid Flow Shop Problem On Machine With Learning Effect

Scheduling is one of the most important branches of operational re-search.Up to now,a large amount of scheduling models have been studied The flow shop problem is one of the scheduling problems.The flow shop can be divided into classical flow shop scheduling and hybrid flow shop scheduling In this thesis,based on image processing,optimal algorithms are proposed for hybrid flow shop schedule of identical jobs on two machines(named as M1 and M2)with learning effect.In image processing,we process several programs Each program consists of two parts:data processing and graphic processing Data processing should precede image processing.Data processing can be done by any CPU(Central Processing Unit)and GPU(Graphic Processing Unit),and graphic processing can only be processed by the GPU.In our problem,each job has two tasks,named as task A and task B respectively,and two optional processing modes.The task B can start to be processed only if after task A has been finished.The first processing mode,named as mode 1,is to assign both task A and B to machine M2.The second processing mode,named mode 2,is to assign task A and B to machine M1 and M2,respectively.It is assumed that each machine has learning effect when processing the job,in other words,the actual processing time of the job is related to the processing position of the jobThis thesis mainly focuses on the hybrid flow shop scheduling problem with no and infinite buffer situations.Our objective is to minimize the makespan.The optimal schedules are given for the two situations,respec-tively.The hybrid flow shop schedule that is better than classic flow shop schedule.In the thesis,the main research contents are summarized as followsThe first chapter introduces basic problems such as combination optimiza-tion problems,scheduling problems,flow shop problems and learning effectsThe second and third chapters research the hybrid scheduling problem for jobs with the same size on two-machine with learning effect.The objective function is to minimize makespan.The difference is that the second chapter studies model with an infinite buffer,and the third chapter studies another model without buffer.Both chapters 2 and 3 give the optimal algorithms and prove them.We have compared the hybrid flow shop schedule with the classical flow shop scheduleOver result,a summary research the optimal algorithm in Chapters 2 and 3.And the differences of the optimal algorithm are summarized between the hybrid type and the classic type.The future research directions are prospected in the section.