可控任务加工时间条件下的多机床生产调度问题研究

In most deterministic scheduling problems, job-processing times are regarded as constant and known in advance. However, in many realistic manufacturing environments, job-processing times can be controlled by the allocation and consumption of the extra resource. In this project, a set of multi-machine scheduling problems with controllable job-processing times will be studied. When job-processing times become controllable, the scheduling problems can describe the realistic manufacturing environments more accurately, and provide better support for managers both in theory and in application. The problems are NP hard, therefore it is very difficult to obtain the optimal solution. However, when the near-optimal solution is acceptable, it is possible to obtain algorithms with relatively higher efficiency by taking the advantage of the special structural characteristics that the problems own. Based on this observation, in this project a kind of algorithms comprised of random optimization, tabu-search, and linear or non-linear programming approaches will be designed, which solve the problems in a divide and conquer manner, dealing with sub-problems such as searching for feasible solution sub-space, optimizing discrete and continuous decision variables in phase. As a whole, this project can provide solutions for the multi-machine scheduling problems with controllable job-processing times, and can also provide usful experience for the mixed optimization problems.

经典调度理论研究中，一般假设任务具有固定已知的加工时间。然而，在大量现实生产环境中，任务往往具有弹性可变的加工时间，可以通过分配和消耗额外的资源加以压缩控制。本项目研究一类可控任务加工时间条件下的多机床生产调度问题，该问题可更为准确地描述现实生产环境中常见的一类生产调度问题，为管理人员提供理论依据与应用指导。该问题是一类具有NP计算难度的混合优化问题，求解难度较高，但在放宽解的最优性要求后，则可利用其特殊的结构特点，合理分解问题，降低算法设计难度，获得可兼顾计算效率和解质量的调度算法。基于这一观察，本项目研究一类由随机优化算法、禁忌搜索算法和连续优化算法协同工作的多机床调度算法，以分而治之的策略，分阶段解决该问题中存在的可行解空间定位问题，及离散和连续决策变量优化问题。本项目能够对一类可控任务加工时间条件下的多机床调度问题提供理论与应用支持，也能够为混合优化问题的研究提供一定的思路与借鉴。

本课题研究可控任务加工时间条件下的生产调度问题。经典生产调度理论中，通常将任务加工时间看作固定且已知的参数，而在大量实际生产活动中，加工时间往往可以通过额外分配和消耗资源加以压缩和控制，从而对生产活动加以进一步控制。将可控任务加工时间引入调度理论研究中，有助于进一步提高生产管理水平，增强企业核心竞争力，因而在国际范围内引起了广泛关注。但是，该条件的引入也将调度问题扩展为线性或非线性混合优化问题，进一步增加了研究困难。本课题基于该类问题的结构特点，将其分解为相互耦合的连续优化问题(最优资源分配)和组合优化问题(机床分配及加工顺序)，以降低算法设计难度。基于该方法，课题研究了双机床流水线调度问题，设计了非线性最优资源分配算法，和加工顺序启发式算法及禁忌搜索算法；研究了双机床加工中心调度问题，设计了非线性最优资源分配算法，和加工顺序启发式算法；研究了并行机床调度问题，设计了线性最优资源分配算法，和机床分配及加工顺序禁忌搜索算法。