Branch-and-Bound algorithms to minimize total weighted and total completion time for the dedicated two-processor task scheduling problems P2fixj∑wjCj and P2fixj∑Cj

摘要：

In this paper, we consider two-processor task scheduling problems on dedicated processors in order to minimize total weighted and total completion times. In these problems, a set of tasks using one or two processors simulta-neously is to be scheduled and no preemption is allowed. Both problems are known to be NP-Hard in the strong sense. Lower bounds and heuristics from the literature are studied and adapted to these problems. A set of dom-inance properties are established. Branch-and-Bound algorithms are developed and tested on a set of randomly generated instances.

关键词： Scheduling Branch-and-Bound Multiprocessor tasks Total weighted completion time

作者: Adel MANAA Chengbin CHU Alice YALAOUI

作者单位: Institut Charles Delaunay -OSI CNRS FRE 2848 Universite de Technologie de Troyes,12 rue Marie Curie-BP 2060 1010 Troyes Cedex -France

会议类型: 国际会议

会议名称: 工业工程与系统管理2007年国际会议(International Conference on Industrial Engineering and Systems Management)(IESM 2007)

会议地点: 北京

会议语种:英文

在线出版日期: 2007-05-30（万方平台首次上网日期，不代表论文的发表时间）