【作者】 徐开亮；

【导师】 冯祖仁；

【作者基本信息】 西安交通大学 ， 控制科学与工程， 2010， 博士

【摘要】 在传统的调度理论研究中,待加工任务的加工时间通常被看作是固定且已知的离散量,调度算法仅仅需要确定任务的机床分配,以及每台机床上任务的加工顺序,以实现对于特定目标函数的优化。然而,在很多现实生产环境中,任务加工时间可以通过在加工过程中分配和消耗一定数量的额外资源加以控制。这些资源包括人力资源、电力、燃气和资金预算等。可控任务加工时间的引入能够减少调度理论研究与现实生产应用之间的差异,同时增加调度算法的灵活性。然而,由于加入了更多的计算变量,调度问题的计算复杂度也随之急剧增加。事实上,作为传统的固定任务加工时间条件下的调度问题的扩展,绝大多数任务加工时间可控条件下的调度问题均具有NP难度。由于这一原因,尽管这一领域中最早的研究报告可追溯到1980年,就目前为止,多数研究仍然主要集中于相对较为简单的问题之上,其中绝大多数为单机床环境下的调度问题,与实际的应用需求相比,仍有较大差距。理论研究与应用需求之间的巨大差距促成了本文的研究工作。本文所做研究主要集中于若干相对而言较为接近现实生产环境的,任务加工时间可控条件下的单机床调度问题与多机床调度问题。由于这类问题大都具有MP难度,和相对较为复杂的约束条件,难以在有限时间内求得最优解,因此本文致力于结合现代优化算法和经典优化算法,力图在可接受计算时间内,为具有现实意义的大规模问题构造令人满意的近优解。本文所完成的工作仅仅是这一充满挑战与乐趣的研究领域中的一小部分,包括了以下内容：1.单机床环境下,具有独立任意到达时间和交货日期的任务的调度问题。调度算法旨在避免交货延时,同时最小化总资源消耗量。(a)首先,为离散时间条件下、连续时间线性资源消耗函数条件下,和连续时间非线性凸资源消耗函数条件下的资源分配问题构造了多项式时间最优算法；(b)其次,构造了用于搜索加工序列的分支定界算法,该算法能够在可接受计算时间内为中小规模问题构造最优解；(c)最后,构造了用于搜索加工序列的禁忌搜索算法,该算法能够在可接受计算时间内为较大规模问题构造最优解或近优解。2.单机床环境下,最小化总加工延迟时间调度问题。调度算法旨在控制所有任务的总交货延迟时间不大于一定预设值,同时最小化总资源消耗量。文中为所有任务具有相同交货时间这一特例构造了多项式时间最优算法。3.并行机床环境下,具有独立任意到达时间和交货日期的任务的调度问题。调度算法旨在避免交货延时,同时最小化总资源消耗量。文中通过禁忌搜索算法对单机床调度算法加以扩展,使之能够在可接受计算时间内为较大规模问题构造最优解或近优解。4.并行机床环境下,具有加工顺序约束条件的任务调度问题。调度算法旨在提供最晚完成时间不大于预设值的解,同时最小化总资源消耗量。(a)首先,在离散时间条件下构造了一个基于贪婪法则的资源分配算法；(b)其次,构造了一个禁忌搜索算法,用于在可接受计算时间内,为较大规模问题提供近优解。如前所述,本文所做工作仅仅是对可控任务加工时间条件下的调度问题的初步尝试与探索,在这一领域中,仍然存在有大量的研究工作有待深入,而这也正是这一领域充满吸引力的原因所在。因此,我们将致力于在今后的工作中继续深化对于这一类问题的研究,以期在理论和实践应用中取得更大的成果。更多还原

【Abstract】 In most traditional deterministic scheduling problems, job-processing times are re-garded as discrete constant known in advance, and the scheduling algorithm only needs to assign jobs to machines and to determine the job-processing permutation on each machine. However, in many realistic manufacturing environments, job-processing times can be con-trolled by allocating extra resource to jobs. Examples of such resource includes human resource, electricity power, gas and cash. The introduction of controllable job-processing times shortens the gap between theoretical research and realistic application, and enhances the flexibility of the scheduling algorithm. However, as more decision variables are added, the computational complexity of the scheduling problems also increases greatly. In fact, as the generalization of the traditional scheduling problems that have constant job-processing times, most of the scheduling problems with controllable job-processing times are NP-hard. For this reason, although the first research report of this field can be traced back to 1980, so far most research work still concerns on relatively simple scheduling problems, most of them focus on single machine environments.The great gap between realistic requirement and theoretical research inspired our work. In this paper, we concern on several single machine and multi-machine deterministic scheduling problems with controllable job-processing times, and provide optimal or near optimal solution for problems of the real-world size. The accomplished work is only the start of a long-term research on this interesting and valuable field, further research work will be continued. Following research result will be introduced in this paper:1. Single machine scheduling with independent job release dates and due dates. The scheduling algorithm is intended to avoid delay of shipment and to minimize total resource consumption.(a) We introduced polynomial time optimal resource allocation algorithms for schedul-ing problems in discrete time environment, and problems in continuous time envi- ronment with linear resource consumption function and non-linear convex resource consumption function;(b) We introduced a branch and bound algorithm for searching for the optimal job-processing permutation for small-and media-sized problems;(c) We introduced a tabu-search algorithm for searching for the optimal or near op-timal job-processing permutation for the real-world-sized problems.2. Single machine scheduling with total tardiness criteria. The scheduling algorithm is intended to make sure that total tardiness will not exceed a given requirement while the total resource consumption is minimized. We introduced a polynomial time optimal algorithm for the special case where jobs have a common due date.3. Parallel machine scheduling with independent job release dates and due dates. The algorithm is intended to avoid delay of shipment and to minimize total resource con-sumption. We extended the researching result on single machine scheduling problem to parallel machines, and introduced a tabu-search algorithm to provide optimal or near optimal solution for the real-world-sized problems.4. Parallel machine scheduling with job-processing precedence constraints. The algo-rithm is intended to provide a solution with makespan no larger than the requirement and minimum total resource consumption.(a) We introduced a greedy algorithm for the resource allocation problem in discrete time environment;(b) We introduced a tabu-search algorithm to provide solution for real-world-sized problems.The research work of this paper is just the beginning of our work in the field of scheduling jobs with controllable job-processing times. In this field, there exist still a great number of research work that is waiting for exploration, which is the main reason that the field is full of attraction. Thus, in the following work we will devote ourselves deeper into this field, and work for further achievement both in theory and in application.更多还原