《《含特殊工件和周期维护的平行机调度》》-毕业论文设计（学术).doc

毕业论文 含特殊工件和周期维护的平行机调度 学 院：理学院 专 业：数学与应用数学 二零一二年六月 English Title Parallel Machine Scheduling with Special Jobs and Periodic Maintenance School : School of science Profession : Mathematics and applied mathematics June 2012 摘 要 调度在各行业有着广泛的应用。本文研究了一类含特殊工件的平行机调度问题。这里我们仅考虑两台机器的情况，其中每台机器均需要周期维护，维护间隔依赖于机器，特殊工件仅被允许在维护后的一定的时间区间内加工，普通工件可以在机器维护之外的任何时刻加工，所有的工件均不可中断，目标是最小化时间表长。 我们首先建立了一个数学规划模型，并基于经典的LPT算法提出了一个新算法，即nsTT算法。其次为了分析该算法的性能，我们给出了目标函数最优值的两个下界。数值实验表明，由该算法求出的解其误差率几乎都在10%以下。这表明nsTT算法的性能较好。但由于一些实际因素的限制，此算法仅适合用求解小规模和中等规模的问题。最后，本文分析了一些参数的变化对调度方案的影响。 关键词：周期维护; 平行机调度; LPT算法; 特殊工件; 数学规划模型 ABSTRACT Scheduling has a wide range of applications. This thesis studies a class of parallel machine scheduling problems with special jobs. We only consider the two parallel machine case, where each of the two machines is required to be maintained periodically while the maintenance period depends on the machine, special jobs can only be allowed to be processed within a certain time interval after a maintenance, normal jobs can be processed everywhere except the machine maintenance periods, the objective is minimizing the makespan. We first establish a mathematical programming model, and proposed a new algorithm named nsTT based on the classical LPT algorithm. Then, in order to analyses the performance of the nsTT algorithm, we propose two lower bounds for the optimal value of the objective function. The computational results show that the error ratios of the schedules produced by the algorithm are almost less than 10%, indicating that the performance of the algorithm is good. However, due to the constraints of some actual factors, this thesis presents some analysis of the impacts of some parameters on the schedules. Key words: periodic maintenance; parallel machine scheduling; LPT algorithms; special jobs; mathematical programming model 目 录 绪论 1 1. 调度的预备知识 2 1.1 调度的概念 2 1.2 平行机调度 2 1.3 周期维护 3 1.4 特殊工件 3 2. 提出问题与问题分析 4 2.1 提出问题 4 2.2 问题分析 4 3. 数学规划模型与MATLAB求解 6 3.1