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

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.

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

调度问题研究是运筹学与组合优化研究的重要分支，其在信息处理、供应链管理和生产制造领域具有广泛应用前景。本项目研究了若干源于生产制造和供应链管理中的复杂调度问题模型，研究的核心是这些问题的近似算法设计和最坏情况界的分析。分别研究了三大类问题。第一类是源于生产制造中的复杂调度问题模型，包括加工时间具有一致性关系的两阶段混合流水作业排序问题、两台批处理机流水作业调度问题和流水作业环境下中间带运输的调度问题等9个子问题。第二类是算法博弈在调度理论中的应用，研究了一类工件具有恶化效应的平行机排序博弈问题。第三类问题研究供应链管理中的一些组合优化问题，例如一类在线库存问题和复杂情况下的场内生产物流调度问题等5个子问题。项目共发表20余篇，其中SCI或EI检索论文13篇。共培养硕士研究生4人和博士研究生2人。项目的研究极大地丰富了调度理论研究的方法和技巧，并且对于调度理论在生产制造和供应链管理等领域的应用具有重要的意义。