caa a22 4500 445838698 CHVBK 20180317145337.0 cr unu---uuuuu 170323e20110801xx s 000 0 eng 10.1007/s10951-010-0172-2 doi (NATIONALLICENCE)springer-10.1007/s10951-010-0172-2 A best online algorithm for unbounded parallel-batch scheduling with restarts to minimize makespan [Elektronische Daten] [Jinjiang Yuan, Ruyan Fu, C. Ng, T. Cheng] We consider online scheduling with restarts in an unbounded parallel-batch processing system to minimize the makespan. By online we mean that jobs arrive over time and all the information on a job is unknown before its arrival time (release date) and restart means that a running batch may be interrupted, losing all the work done on it, and the jobs in the interrupted batch are released and become independently unscheduled jobs. It is known in the literature that the considered problem has no online algorithm with a competitive ratio less than $(5-\sqrt{5})/2$ . We give an online algorithm for the considered problem with a competitive ratio $(5-\sqrt{5})/2\approx 1.382$ . Springer Science+Business Media, LLC, 2010 Parallel-batch scheduling nationallicence Online algorithm nationallicence Restart nationallicence Competitive ratio nationallicence Yuan Jinjiang Department of Mathematics, Zhengzhou University, 450001, Zhengzhou, Henan, People's Republic of China aut Fu Ruyan School of Sciences, China University of Mining and Technology, 221116, Xuzhou, Jiangsu, People's Republic of China aut Ng C. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong aut Cheng T. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong aut Journal of Scheduling Springer US; http://www.springer-ny.com 14/4(2011-08-01), 361-369 1094-6136 14:4<361 2011 14 10951 https://doi.org/10.1007/s10951-010-0172-2 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s10951-010-0172-2 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Yuan Jinjiang Department of Mathematics, Zhengzhou University, 450001, Zhengzhou, Henan, People's Republic of China aut NATIONALLICENCE 700 1- Fu Ruyan School of Sciences, China University of Mining and Technology, 221116, Xuzhou, Jiangsu, People's Republic of China aut NATIONALLICENCE 700 1- Ng C. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong aut NATIONALLICENCE 700 1- Cheng T. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong aut NATIONALLICENCE 773 0- Journal of Scheduling Springer US; http://www.springer-ny.com 14/4(2011-08-01), 361-369 1094-6136 14:4<361 2011 14 10951 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer