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

项目名称： 若干新型车间作业排序问题研究

项目编号： No.11501512

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

立项/批准年度： 2016

项目学科： 数理科学和化学

项目作者： 董建明

作者单位： 浙江理工大学

项目金额： 18万元

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

中文关键词： 车间作业排序；两阶段排序；计算复杂性；近似算法

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

英文关键词： Shop Scheduling;Two-stage Scheduling;Computational Complexity;Approximation Algorithm