带批运输的流水调度模型与算法研究

Flowshop scheduling problem is a classical scheduling problem ,which is widely used in management science, computing science and engineering technology and is a very active branch in OR research field in recent years. In this project, we intend to carry on the further research on flowshop scheduling with batch transport. We explore and research mainly on the approximate algorithms considering the same size of processed jobs and the different size of jobs , the optimal algorithms when given specific conditions. . The main targets of the project include:. (1) When the sizes of all jobs are same, we research on the relationship between scheduling model with batch transportation and the classical three machines scheduling problem ,then give the better approximate algorithm;. (2) When the sizes of all jobs are different, a better approximation algorithm is given by combining the bin packing problem and the approximate algorithm of flowshop scheduling;. (3) According to the flowshop scheduling model with batch transportation, we propose the optimal algorithm in some given conditions;

带批运输的流水调度问题，是经典流水调度问题的推广, 它广泛地应用于管理科学、计算科学和工程技术等领域, 近年来流水调度模型的研究是运筹领域一个非常活跃的分支。本项目将对带批运输的流水调度模型展开进一步深入研究，主要考虑从待加工工件的体积相同，工件体积大小不同的角度研究此类问题的近似算法，以及特定情况下探寻最优算法。. 课题的主要研究目标包括：. （1）当工件体积大小相同时，研究批运输的流水调度模型和经典三台流水机器调度问题的关系，并且由此给出更好的近似算法；. （2）当工件体积大小不同时，通过结合装箱问题的算法和流水调度的近似方案，给出更好的近似算法； . （3）针对带批运输的流水调度模型，提出在某些特定条件下的最优算法。

组合优化是运筹学中的一个经典且重要的分支，所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等诸多领域。以该项目为依托，本项目组主要研究组合优化中的调度问题、背包问题及排课问题。.该项目重要结果如下：共计产出6篇文章，其中SCI见刊1篇，SCI已录用2篇，国内核心2篇，投稿中1篇。具体如下：.1.第1阶段单机第2阶段多同型平行机的流水调度模型，分别给出3 和的近似算法，改进了前人对该模型的研究结果。对第2阶段有2台和3台的特殊情况，而出了近似比为2.5和2.67的线性时间复杂度算法。成果发表在《Journal of Combinatorial Optimization》和《应用数学学报》期刊上。.2.考虑了带运输时间两台平行机调度，给出了新的近似比1.5+ε，改进了以前的1.5556，文章发表在期刊：《Journal of Combinatorial Optimization》，目前状态已接收录用https://doi.org/10.1007/s10878-020-00593-1。.3.研究了冲突图上背包问题，给出了新的分支定界算法，比现有算法快，且解出的最优解也较多，文章投稿在：《Asia-Pacific Journal of Operational Research》，目前状态已录用。.4.研究了两台机器流水调度模型的近似算法，给出了和的一个PTAS，文章投稿在：《Theory of Computing Systems》，目前状态审稿中。.5.研究了新中考的排课问题。一般情况下约束和变量是上百万级的，无法求解。作者利用整数规划建模，然后把该问题转化成多阶段问题，每个阶段给出小问题的解，这样使得问题的求解变得可行。文章投稿在：《运筹学报》，目前状态已录用。