带冲突约束两台平行专用机排序的一个改进算法

摘要：

研究带冲突约束的两台平行专用机排序问题的一种特殊情形,针对极小化工件最大完工时间的目标函数,与已有的5/3-近似算法相比,考虑了一类专属工件的加工,并对时间窗口作出改进,得到新算法的近似比为 √5+1/2,并给出了紧例.

关键词：平行专用机排序、冲突约束、近似算法、近似比

所属期刊栏目：42

分类号：O221.7(运筹学)

资助基金：国家自然科学基金;国家自然科学基金;浙江省自然科学基金资助项目

在线出版日期：2022-06-17（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：90-94