| 三台平行机上四个约束链的排序问题 |
| |
| 引用本文： | 栾文婕.三台平行机上四个约束链的排序问题[J].聊城大学学报(自然科学版),2011(4):37-40,51. |
| |
| 作者姓名： | 栾文婕 |
| |
| 作者单位： | 曲阜师范大学管理学院 |
| |
| 基金项目： | 国家自然科学基金(11071142);山东省自然科学基金(ZR2010AM034) |
| |
| 摘 要： | 考虑四条优先约束链的n个工件在三台平行机上的排序问题,目标是极小化最大机器完工时间.文中说明此问题至少为NP-hard的,并通过一个伪多项式时间算法和一个完全多项式时间近似规划来描述此问题的复杂性.
|
| 关 键 词： | 排序 约束链 动态规划 计算复杂性 FPTAS |
Scheduling Four Chains on Three Parallel Machines |
| |
| LUAN Wen-jie.Scheduling Four Chains on Three Parallel Machines[J].Journal of Liaocheng University:Natural Science Edition,2011(4):37-40,51. |
| |
| Authors: | LUAN Wen-jie |
| |
| Institution: | LUAN Wen-jie(School of Management,Qufu Normal University,Rizhao 276826,China) |
| |
| Abstract: | A problem of scheduling n tasks with four chain-precedence constraints on three parallel machines is considered.The objective is minimize the makespan.This paper explain the NP-hardness of this problem,which computational complexity is characterized by giving a pseudo-polynomial time algorithm and a FPTAS. |
| |
| Keywords: | scheduling chain-precedence constraints dynamic program computational complexity FPTAS |
| 本文献已被 CNKI 等数据库收录！ |
