复杂生产制造环境下的排序问题研究

项目名称： 复杂生产制造环境下的排序问题研究

项目编号： No.11471286

项目类型： 面上项目

立项/批准年度： 2015

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

项目作者： 胡觉亮

作者单位： 浙江理工大学

项目金额： 70万元

中文摘要： 排序问题是组合优化方向研究较为活跃的一个分支，排序环境的复杂化是现代排序问题的一个主要特征。大量的排序问题源于生产制造领域，本课题将深入研究若干复杂生产制造环境下的排序问题，核心是算法的设计与分析。具体包括研究工件带装、卸载的排序问题和两类混合车间作业排序问题，分析问题的计算复杂性并设计高效的近似算法和算法的最坏情况界分析；研究供应链背景下的加工与运输协同的排序问题和生产制造中涉及竞争与协作的博弈排序问题，设计高效的近似算法和最坏情况界分析，并研究博弈排序环境下纳什均衡存在的条件和性能的定量分析。对这些问题的研究将在理论上丰富排序研究的问题、模型和算法，同时将拓宽排序问题的实际应用领域，是一项有创造性和前瞻性的研究工作。

中文关键词： 排序；近似算法；最坏情况界；博弈排序

英文摘要： Scheduling is one of active branches in operations research and combinatorial optimization, and the scheduling environments are becoming more and more complicated in modern scheduling. Many scheduling problems arise in manufacturing environments. The project will extensively study several scheduling problems in complex manufacturing environments, and mainly focus on the algorithm design and analysis. To make more concrete, study scheduling problems with job loading and unloading and two hybrid shop scheduling problems. The complexities of problems are studied, as well as design of approximation algorithms and the worst-case ratio analysis. Study scheduling problems with transportation considerations and scheduling game involving competition and cooperation in supply chain environments. Design approximation algorithms and give the worst-case ratio analysis. Discuss the existence of a Nash equilibrium and analyze the system efficiency quantitatively for the scheduling game. It should be emphasized that our research not only helps enrich the scheduling theory in contents and skills of algorithm design and analysis, and also broaden the application of scheduling. It will be one prospective and innovative research.

英文关键词： Scheduling;Approximation algorithms;Worst-case ratio;Scheduling game