带运输机的流水调度的复杂性研究

发布时间：2019-05-05 06:33

【摘要】：流水调度问题(flow shop)是近几十年来调度算法研究的重点问题模型,也是车间生产过程中涉及较多的一类模型。流水调度问题可定义为：有m台处理机,来处理n个作业,每个作业在每台处理机上都有一定的处理时间,所有作业都有相同的加工顺序,每台处理机只处理一道工序,且每台处理机一次只能处理一个作业,该问题的目标就是得到一个可行调度方法,使得完成所有作业所用的时间最短。之前很多文献对该问题进行了研究,但多数研究都是假设的理想状态下的问题模型,不是忽略两台处理机之间的运输时间,就是认为负责运输的运输机的容量是无限的。而本文则明确考虑了运输机的运输时间和容量,从而进行对该模型的计算复杂性的分析和研究。本文研究的是有两台处理机和一台运输机的流水线调度问题。在这个问题中,两台处理机A和B处理n个作业,这些作业串行的在每台处理机上处理,其在每台处理机上的处理时间是确定的,且所有作业必须先在处理机A上处理,然后再运输到处理机B上处理,有一台运输机负责将作业从处理机A运输到处理机B,运输时间是不依赖于作业的,每台处理机有无限个缓存区来存放待处理的和处理完成的作业。本文主要讨论了当运输机的容量为1、容量为2、容量大于或者等于3的三种问题模型的计算复杂性。运输机容量为1和容量大于或者等于3的情况,已在前人的研究成果中被证明出是强NP-hard问题,本文通过改变运输时间条件重新构造实例,用更详细的分析过程证明出这两个模型是强NP-hard问题,同时说明了两种证明方法的等价性。运输机容量为2的问题模型在以往的文献中一直是一个开放问题,没有文章进行专门的研究,但本人已经在去年的一篇拟发表的文章中证明出来该问题是一个强NP-hard问题,本文重点说明了该证明方法和容量为1的模型的证明方法的等价性。最后,本文还研究了运输时间依赖于作业的处理时间的有两台处理机的流水调度问题模型,主要分析了每个作业的运输时间是其在第一台处理机上的处理时间的2倍的情况,我们证明出了该问题是可解的,并且给出了一个对约翰逊规则进行了扩展的算法来解决该问题。
[Abstract]:The pipelining scheduling problem (flow shop) is the key problem model of scheduling algorithm research in recent decades, and it is also a kind of model involved in the workshop production process. Pipelining scheduling problem can be defined as: there are m processors to handle n jobs, each job has a certain processing time on each processor, all jobs have the same processing sequence, each processor only handles one process. And each processor can only deal with one job at a time. The goal of this problem is to obtain a feasible scheduling method to minimize the time it takes to complete all jobs. Many previous literatures have studied the problem, but most of the studies are hypothesized ideal model of the problem, either neglecting the transport time between two processors or considering that the capacity of the transport aircraft responsible for transport is infinite. In this paper, the transport time and capacity of the transporter are explicitly considered, and the computational complexity of the model is analyzed and studied. In this paper, the pipeline scheduling problem with two processors and one transporter is studied. In this problem, two processors A and B process n jobs, which are processed serially on each processor, and their processing time on each processor is determined, and all jobs must first be processed on processor A. Then it was transported to processor B for processing, and a transporter was responsible for transporting the operation from processor A to processor B. the transport time was independent of the operation. Each processor has unlimited cache areas to store pending and processed jobs. In this paper, the computational complexity of three problem models with capacity of 1, capacity of 2 and capacity of more than or equal to 3 is discussed. When the capacity of the transporter is 1 and the capacity is greater than or equal to 3, it has been proved to be a strong NP-hard problem in the previous research results. This paper reconstructs an example by changing the transportation time condition. The two models are proved to be strong NP-hard problems by a more detailed analysis process, and the equivalence of the two methods is also illustrated. The problem model with transport plane capacity of 2 has been an open problem in the past literature, and there is no special research on it, but I have already proved that this problem is a strong NP-hard problem in a paper to be published last year. This paper focuses on the equivalence of the proof method and the proof method of the model with capacity 1. Finally, the pipelining scheduling model with two processors is studied, in which the transport time depends on the processing time of the operation, and the transport time of each job is analyzed to be twice the processing time of each job on the first processor. We prove that the problem is solvable and give an algorithm to extend Johnson's rule to solve the problem.
【学位授予单位】：大连理工大学
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TB497

【共引文献】