| 机器带故障的两台机排序问题的一个近似算法 |
| |
| 引用本文： | 叶赛英,沈灏,魏小兰.机器带故障的两台机排序问题的一个近似算法[J].杭州电子科技大学学报,2008,28(2):90-92. |
| |
| 作者姓名： | 叶赛英 沈灏 魏小兰 |
| |
| 作者单位： | 杭州电子科技大学理学院,浙江,杭州,310018 |
| |
| 基金项目： | 浙江省教育厅资助项目
,
浙江科技学院校科研和教改项目 |
| |
| 摘 要： | 讨论机器带故障中断的两台平行机排序问题，目标为极小化误工工件数，在转移时间t=0时的排序问题是问题P2｜D=∞，t=0｜∑u′ij，该文给出了相应的算法，并利用该算法，考虑了当工件转移时间t〉0时的NP难的排序问题P2｜D=∞，t≠0｜∑u′ij。该文使用对前一问题的最优序π^＊当中的工件相交换，使得增加误工工件数尽量少的方法，提出了一个差界为1的多项式时间的近似算法，并给出了证明及算法的计算复杂性。
|
| 关 键 词： | 近似算法 最坏情况界 机器中断 |
| 文章编号： | 1001-9146(2008)02-0090-03 |
| 修稿时间： | 2007年9月4日 |
An Approximation Algorithm for Two Parallel Machines Scheduling with Machine Disruptions |
| |
| YE Sai-ying,SHEN Hao,WEI Xiao-lan.An Approximation Algorithm for Two Parallel Machines Scheduling with Machine Disruptions[J].Journal of Hangzhou Dianzi University,2008,28(2):90-92. |
| |
| Authors: | YE Sai-ying SHEN Hao WEI Xiao-lan |
| |
| Affiliation: | ( The School of Science, Hangzhou University of Electronic Engineering, Hangzhou Zhejiang 310018, China) |
| |
| Abstract: | The problem of two parallel machines scheduling with machine disruptions is discussed with the objective of minimizing the sum of unit penalties. If transfer time t=0, the problem P2｜D=∞,t=0｜∑u′ij is P problem, and an algorithm is proposed. Using this algorithm, we consider the NP - hard problem P2｜D=∞,t≠0｜∑u′ij. The method is exchanging the jobs of π^＊ and minimizing the adding sum of unit penalties. Then an approximation algorithm is proposed in this paper and its difference bound is 1. |
| |
| Keywords: | approximation algorithm worst case bound machine disruptions |
| 本文献已被 维普 万方数据 等数据库收录！ |
|
