三台平行机上四个约束链的排序问题
栾文婕
曲阜师范大学管理学院,山东日照,276826
摘要：考虑四条优先约束链的n个工件在三台平行机上的排序问题,目标是极小化最大机器完工时间.文中说明此问题至少为NP-hard的,并通过一个伪多项式时间算法和一个完全多项式时间近似规划来描述此问题的复杂性.
关键词：排序约束链动态规划计算复杂性FPTAS
分类号：O241(计算数学)
资助基金：国家自然科学基金(11071142)山东省自然科学基金(ZR2010AM034)
论文发表日期：2011-01-01
在线出版日期：2026-08-28（本平台首次上网日期，不代表文献的发表时间）
页数：5( 37-40,51 )
英文信息