|
|||||
|
|
Online scheduling on two parallel-batching machines with limited restarts to minimize the makespan |
|
| Authors: | Ruyan Fu CT Ng |
| Affiliation: | a School of Sciences, China University of Mining and Technology, Xuzhou, Jiangsu 221116, People's Republic of China b Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong SAR, People's Republic of China c Department of Mathematics, Zhengzhou University, Zhengzhou, Henan 450052, People's Republic of China |
| Abstract: | We study online scheduling on two unbounded parallel-batching machines with limited restarts to minimize the makespan. In this system jobs arrive over time and a batch can be restarted if and only if all the jobs in it have never been restarted. To tackle this difficult problem, we make the second-restart assumption whereby we can only interrupt a running batch B at time t if both machines are busy at time t and batch B has a later starting time than the other running batch. For this case, we provide a best online algorithm with a competitive ratio  . For the general problem, we show that no online algorithms can have a competitive ratio less than 1.298, leaving a gap from 1.298 to 1.366. |
| Keywords: | Online scheduling Parallel-batching machines Limited restart Competitive ratio Analysis of algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ | |