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

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

项目编号： No.61203183

项目类型： 青年科学基金项目

立项/批准年度： 2013

项目学科： 自动化学科

项目作者： 徐开亮

作者单位： 西安理工大学

项目金额： 25万元

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

中文关键词： 生产调度；可控任务加工时间；混合优化；启发式算法；禁忌搜索

英文摘要： 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 mult

英文关键词： Schedule；Controllable job-processing time；Mixed optimization；Heuristic algorithm；Tabu-search