若干新型车间作业排序问题研究

Scheduling is an active branch in operations research and combinatorial optimization, in which, the models of shop scheduling might be of the most importance that have a wide application prospect. Motived by the manufacturing and information processing applications, and by the promotion from both theory and its application, shop scheduling models become more and more complicated and lots of new problems are springing up. The project mainly study some of these new problems, including the two-stage open shop scheduling problems, the two-stage parallel processing flow shop scheduling problems, the proportionate flow shop(open shop) scheduling problems and the open shop scheduling problems with machine-dependent job processing time. We aim at studying the model characteristics of these complex and new scheduling problems, analyzing the properties of optimal schedules and feasible schedules, analyzing the complexity of problems, designing optimal or approximation algorithms and with worst-case ratio analysis. Creating effective and systematic methods for these problems, and being greatly expected to get a series of creative research results.

排序问题是组合优化方向研究较为活跃的一个分支，车间作业排序是其中一类重要且具有广泛应用前景的问题。车间作业排序问题源于生产制造和信息处理实践，并随着理论和实践发展的需要派生出众多的复杂问题模型和新问题模型。本课题将会深入研究若干新型车间作业排序问题，具体包括一类新型两阶段自由作业排序问题、两阶段并行流水作业排序问题、加工时间具有一致性的流水作业(自由作业)排序问题和加工时间由机器决定的自由作业排序问题。目的是研究这些新型复杂排序问题的特征，刻画问题最优解和可行解的性质，分析问题的计算复杂性，设计高效的近似算法或最优算法，对近似算法做最坏情况界的分析。建立研究此类车间作业排序问题系统有效的研究方法，并争取获得一系列创新性研究成果。

调度问题研究是运筹学与组合优化研究的重要分支，车间作业调度问题是其中一类重要且具有广阔应用背景的问题。本项目研究了三类共9个车间作业调度问题模型，分别是两阶段并行流水作业调度问题、m台机k阶段并行自由作业调度问题、机器数是输入的并行两阶段流水作业调度问题、两台机m阶段并行自由作业排序问题、两阶段自由作业排序问题、工件具有尺寸的带运输的平行机调度问题、工件具有尺寸的带运输的单机多客户调度问题、加工时间具有一致性关系的三台机自由作业调度问题和一类加工时间具有一致性关系的三台机混合作业调度问题。对于这些问题的研究，我们给出了问题的（完全）多项式时间近似方案或改进的多项式时间近似算法，并给出了算法的最坏情况界证明。项目共发表或录用论文7篇，其中SCI或EI检索论文5篇，已投稿论文4篇。共培养硕士研究生4人。项目的研究极大地丰富了调度理论研究的方法和技巧，并且对于调度理论在计算机信息处理、供应链管理和智能生产制造等领域的应用具有重要的意义。