Two-Machine Flowshop Scheduling With Flexible Operations

Two machine flowshop scheduling problem is one of the key branching problem. Jobs considered in classical two machine flowshop scheduling consists two fixed operations processed on two distinct machines seperately, few investigated same operaitons processed on different machines. However, in real processing, it would be common to have several machines in a flowshop that can process the same operations which would be hard to be processed two times or more due to the high cost of machine operating. So this kind of flexible operation scheduling should be investigated. This paper discussed jobs with flexible operations, modified models based on whether due date is contained separately, designed and proposed algorithms to obtain optimal schedule of jobs and flexible operations.Chapter 1 introduced the researching background job scheduling, some related theoretical research are also summarized in this chapter, then the literature review is divided into three parts which are the research statuses of two machine flowshop scheduling problem, two machine flowshop with flexible operations and two machine flowshop with due date.Chapter 2 mainly investigated jobs with flexible operations in two machine flowshop without due date consideration to minimize the total completion time. Relevant model was modified, lemmas and properties are derived to analyze the completion times of jobs when the initial schedule of jobs and operations are changed. Algorithm AGi is derived to optimize the schedule of flexible operations in a given order of jobs, Also, the improved SPT algorithm which is called algorithm AG2 is derived to obtain an optimal schedule of jobs, computational experiments were then presented to verify the accurency and efficiency of both algorithms. A special occasion that identical jobs in two-machine flowshop with flexible operations is also dicussed, and the problem is proved to be polynomially solvable.Chapter 3 mainly considered the due date in two machine flowshop with flexible operations, the objective is to minimize the total tardiness. A non-linar optimization scheduling model reflecting the problem is conducted, lemmas and inferences are presented to depict the tardiness change when the schedule of jobs and operations is optimized. Algorithms AG3 was derived to obtain an optimal schedule of flexible operations under any given order of jobs, also, an improved SLACK algorithm AG4 is derived to obtain an optimal schedule of jobs, computational experiments are also provided in verifying the accuracy and efficiency of algorithmsAG3 and AG4.Chapter 4 provided a summary of theoretical results in this paper.