Complexity Research Of Flow Shop Scheduling With One Transporter

Flow shop problem is an important problem model in the research of machine scheduling in the last decades, which is also a kind of model involved in most manufacturing systems. Flow shop problem can be defined as follows:there are some machines with the number of m to process n jobs. Each job on machines has its processing time, and all jobs has the same processing order. Each machine only handles one procedure, and processes only one job at a time. The objective is to determine a feasible scheduling sequence with minimal makespan.Many books and papers have been published in the area of machine scheduling. However, most of the research are about the ideal model, in which they assume that jobs are transported instantaneously from one location to another without transportation time involved or that either there are an infinite number of transporters for delivering jobs. In this paper, we study the flow shop problems with explicit transportation considerations.In this paper, we study a flow shop problem, in which we’re given a set of n jobs and two machines, A and B. These jobs are processed on machines serially. The processing time of these jobs on machines is given, and each job has to be processed on machine A and then on machine B. The jobs have to be transported by a single interstage transporter and the transporting time is independent of the job. There is an unlimited buffer on each machine to store jobs that will be processed or have been finished.The cases that the capacity of transport is1, that the capacity is2and that the capacity is greater than or equal to3are involved. The computational complexity of these cases is discussed. It has been proved in the research achievements of predecessors that the model in which capacity of transport is1and the one in which capacity is greater than or equal to3are strongly NP-hard problem. In this paper, we prove the two kinds of models are strongly NP-hard problem through a new method by changing the conditions of transporting time and reconstructing a new instance. Then the equivalence of the new method and the old one is analyzed. The problem model in which capacity of transport is2has always been an open problem in the literature in the past. There are no specialized books or papers researching this model. Last year, I proved that this problem model is also strongly NP-hard problem in a paper that will be published. In this paper, we will illustrate this method of demonstration and the one that proves the model that capacity is1are isovalent.Finally, we also study a case that the transporting time depends on the processing time of the job. Especially, we analyze the transport time of each job is2times of the processing time of the job on the first machine, and we prove that the problem is solvable, and generalize the Johnson’s rule to solve this problem.