A Job Shop Scheduling Problem in Software Testing
In this paper, we address a special case of job scheduling problem which arises from software testing. Given n jobs and m ma chines, each job should first be operated on machine 1 with a short time d and then be scheduled on one of the rest m-1 machines. Our task is to find an optimal schedule to minimize the maximal makespan of the machines. We show this problem is NP-hard and give two approximation algorithms: the List Scheduling algorithm with the approximation rate 2.5 and the Longest Processing Time First algorithm with the approxi mation rate 1.5.
Jie Zhou Hong Zhu
School of Mathematics and Physics Shanghai Normal University Shanghai Key Laboratory of Trustworthy Shanghai Key Laboratory of Trustworthy Computing East China Normal University Shanghai,China Shangha
国际会议
南宁
英文
19-29
2009-12-04（万方平台首次上网日期，不代表论文的发表时间）