1、 學(xué)校代碼：10255 學(xué) 號：2130854 單機(jī)下最小化最大延遲問題的滾動調(diào)度方法研究 單機(jī)下最小化最大延遲問題的滾動調(diào)度方法研究 ROLLING HORIZON ALGORITHMS FOR THE SINGLE MACHINE MAXIMAL DELAY TIME SCHEDULING PROBLEM WITH RELEASE DATES 學(xué)科專業(yè)：物流工程 作者姓名：王鴿 指導(dǎo)教師：王長軍 答辯日期：2015.5.14

2、 單機(jī)下最小化最大延遲問題的滾動調(diào)度方法研究 II ROLLING HORIZON ALGORITHMS FOR THE SINGLE MACHINE MAXIMAL DELAY TIME SCHEDULING PROBLEM WITH RELEASE DATES ABSTRACT Production scheduling problem is widely concerned since the 1970s, and until n

3、ow still is the research challenge. In the final analysis is for its NP-hard attributes. Although genetic, taboos and other neighborhood algorithm, Job-based, Time-based and other rolling algorithm has a number of studie

4、s, this problems still have research value from the angle of realistic and academic research. This paper is from the perspective of the single machine scheduling problem. And discuss how to get the minimum of maximal del

5、ay time scheduling in a dynamic environment. The problem is a NP hard and it is the basis for the scheduling problem. On the basis of the job dynamic arrival and shortage of the existing rolling scheduling, this paper pr

6、oposes a Collision-Window Based rolling scheduling method. This scheduling strategy uses a new decomposition problem method to make the sub-problem to be a un NP-hard problem, and the scheduling performance is no longer

7、affected by the job release density. This paper proposes the specific algorithm steps of CWB rolling scheduling algorithm. It is to prove that the new algorithm result is more stable and more outstanding under different

8、job release density and different job number, comparing the new algorithm with EDD, 2 kinds of traditional rolling algorithms and other algorithms using C language programming and large-scale simulation. At the same time

9、 the computation speed of the new algorithm is faster compared with the two traditional rolling algorithms due to the polynomial solution of the sub-problem. KEY WORDS: single machine, rolling scheduling, dynamic, releas