批处理机上的分组工件排序研究

Scheduling is one of the important branches of combinatorial optimization. Batching scheduling (including parallel-batch and serial-batch) is a very active research direction in scheduling research in the past two decades. In the production and transportation process, due to the differences of jobs' physical characteristics, chemical features and the processing requirements, the jobs are often classified into different job families (groups), and the jobs in different job families often require different methods and mode of operation. This project mainly studies the models of family-job scheduling on batching machines combinning with the research on the multi-agent schdeuling and the supply chain schduling. The research goal of this project is that: Based on the basic goal to solve the two open problems in the literature, we will present full characterization of the (local) structural properties of the optimal solutions and feasible solutions, this project will create effective and systematic methods and theories, and make innovative research results in computational complexity analysis, design and analysi of approximation algorithms.

排序论是组合最优化的重要分支之一。批处理机（包括平行分批和继列分批）上的排序是排序论领域近二十年来十分活跃的研究方向。在加工生产以及成品运输的过程中,常常由于工件的物理特征、化学特性及加工要求等的差异性而事先将工件划分成不同的工件组（类)，并对不同工件组中的工件采取不同的操作方法和运作方式。本项目主要研究批处理机上的分组工件排序模型，并将与多代理排序和供应链排序的研究相结合。项目的研究目标是：以攻克相关文献中两个遗留问题为基本目标，充分刻画最优解和可行解的（局部）结构性质，创建出系统有效的研究方法和基本理论，从而在计算复杂性分析和近似算法的设计与分析方面做出创新性的研究成果。

排序论是运筹学和组合最优化领域极为活跃的研究分支。在加工生产以及成品运输的过程中，由于工件的物理特征、化学特性及加工要求等的差异性而需将工件划分成不同的工件组，并对不同工件组中的工件采取不同的操作方法和运作方式。本项目将批处理机上的分组工件排序与多代理排序、工件可拒绝排序以及供应链排序相结合，研究了若干具有实际工业生产背景的排序模型。这里主要探讨这类排序问题的计算复杂性，即对可解问题设计多项式时间算法，对NP-困难问题设计近似算法，对在线问题设计在线算法。受本项目资助共发表20篇期刊学术论文，其中11篇SCI期刊论文，1篇EI期刊论文。代表性成果如下：（1）对成组技术加工限制下的两个代理排序问题，证明了目标为最小化延迟和完工时间和情形的强NP-困难性，给出了目标都为最小化最大费用情形的多项式时间算法；（2）对继列分批工件可用性的两个代理排序问题给出了完整的计算复杂性分类；（3）对目标为最大化所有准时工件收益的成比例车间作业的多代理排序问题，证明了代理数任意情形的强NP-困难性，代理数固定情形的一般NP-困难性，并设计了拟多项时间算法和全多项式时间近似方案；（4）对带有到达时间、工件允许拒绝，不同工件类的分批排序问题，设计了2-近似算法和多项式时间近似方案，该结果解决了文献中的一个遗留问题，并改进了前人文献中只有一个工件类的时间复杂性；（5）对带有到达时间且相容性依赖于工件加工时间的分批排序问题，离线情形给出了到达时间个数固定情形的拟多项式时间算法，部分解决了文献中的遗留问题，给出了到达时间个数任意情形的多项式时间近似方案，在线情形设计了最好可能的在线算法；（6）对加工时间是其已加工工件加工时间累积退化效应的供应链排序问题，证明了问题的一般NP-困难性，并设计了全多项式时间近似方案；（7）对工件允许拒绝且带有线性退化维护区间的排序问题，给出了完整的计算复杂性分类。