带机器随机故障和位置相关加工时间的平行机调度问题

发布时间：2018-04-02 06:52

本文选题：调度　切入点：随机干扰　出处：《昆明理工大学》2017年硕士论文

【摘要】：调度是运筹学与控制论学科的重要研究方方向,关于它的论文有很多。在这些经典的调度问题中,通常假设工件的加工时间通常为常数,并且在工件加工过程中机器可以持续加工工件。在这错综复杂的现实生活中,调度问题是不拘一格的,有时工件的实际加工时间随其开始加工时间的推迟而增大,工作效率越来越低;有时工件的实际加工时间随其开始加工时间的推迟而减小,工作效率越来越高;而有些情况下,工件的实际加工时间是与其所排位置相关的。与此同时,由于一些内部的原因和外部环境的限制,会使机器在加工过程中发生中断,使机器不能持续工作。基于此,本文研究带机器随机故障和加工时间与位置相关的平行机调度问题。该问题中,工件的实际加工时间是与其所排位置相关的一般函数。在机器运行过程中,某些随机事件的发生会导致部分机器不能正常工作。本文假设这些随机事件的开始时间已知,且它们会以一定的概率持续一段时间。当随机事件发生时,本文考虑工件可中断和不可中断两种不同的情形下,目标是最小化工件总完成时间的期望。本文将对相应问题不同情形的复杂性进行分析并设计相应的伪多项式时间算法。具体研究内容如下:(1)工件不可中断:在机器数量固定的情况下,证明了相应问题是NP难的,设计了伪多项式时间动态规划算法,进而说明了相应问题是一般NP难的。具体地,本文仅详细分析两台机器中有一台机器发生中断的情况,然后简单讨论如何将结论推广到m台机器中有K台机器会发生中断的情况。(2)工件可中断:在机器的数量变化时,证明了相应的问题是强NP问题;在机器数量为固定值且发生中断的机器大于等于两台的情况下,证明了该问题是NP难的,设计了伪多项式时间动态规划算法,进而说明了相应问题是一般NP难的;然而,当中断仅发生在一台机器上时该问题是否为NP难的仍是未知的。
[Abstract]:Scheduling is an important research direction in operational research and cybernetics, and there are many papers on it.In these classical scheduling problems, the processing time of the workpiece is usually assumed to be constant, and the machine can continuously process the workpiece during the process of the workpiece processing.In this complicated real life, the scheduling problem is not restricted, sometimes the actual processing time of the workpiece increases with the delay of the starting processing time, and the working efficiency becomes lower and lower.Sometimes the actual processing time of the workpiece decreases with the delay of the starting time, and the working efficiency becomes higher and higher. In some cases, the actual processing time of the workpiece is related to the position of the workpiece.At the same time, due to some internal reasons and external environment constraints, the machine will be interrupted in the process of processing, so that the machine can not continue to work.Based on this, the parallel machine scheduling problem with machine random fault and processing time and position is studied.In this problem, the actual processing time of the workpiece is a general function related to the position of the workpiece.In the process of machine operation, some random events will cause some machines to fail to work properly.This paper assumes that the starting time of these random events is known and that they will last for a certain period of time with a certain probability.When random events occur, the goal of this paper is to minimize the expectation of the total completion time of the workpiece in the case of interruptible and uninterruptible workpiece.In this paper, the complexity of the corresponding problems in different cases is analyzed and the corresponding pseudo-polynomial time algorithm is designed.In the case of fixed number of machines, it is proved that the corresponding problem is NP-hard, and a pseudo-polynomial time dynamic programming algorithm is designed, which shows that the corresponding problem is general NP-hard.Specifically, this paper only analyzes the interruption of one of the two machines in detail.Then it is discussed how to generalize the conclusion to the case that K machines in m machines will be interrupted. The workpiece can be interrupted: when the number of machines changes, it is proved that the corresponding problem is a strong NP problem;It is proved that the problem is NP-hard when the number of machines is fixed and the number of machines interrupted is more than two. The pseudo-polynomial time dynamic programming algorithm is designed, and the corresponding problem is proved to be general NP-hard.Whether the problem is NP-hard is unknown when interrupts occur on only one machine.
【学位授予单位】：昆明理工大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O223

【相似文献】