关于平行机排序问题的两点注记 |
| |
引用本文: | 陈志龙,赵小平.关于平行机排序问题的两点注记[J].运筹学学报,1992(1). |
| |
作者姓名: | 陈志龙 赵小平 |
| |
作者单位: | 复旦大学,华东化工学院 |
| |
基金项目: | 本研究得到国家自然科学基金资助 |
| |
摘 要: | 本文考虑了有完工约束的平行机排序问题,证明了问题 pm|T|∑c_i是 NP-完全的,而对问题 pm|T,_i≡p|∑w_ic_i 提出 O(n~2)的算法,并证明其最优性.将 n 个互相独立的工件(工件集 N={1,2,…,n))放在 m 台等速率平行机(机器M={M_i,…,M_m})上加工.已知每个工件必须且仅须在一台机器上加工一次,并且加工时不允许中断.工件 i(i∈N)在不同机器上加工时间不变,设为 p_i,罚权 w_i 也与机器无关,p_i 和 w_i 皆为非负实数.我们将多台机器加工工件的一个安排称为一个时间表.当时间表π确定后,记工件 i 的完工时间为 c_i(π
|
本文献已被 CNKI 等数据库收录! |
|