Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan
- PDF / 495,444 Bytes
- 17 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 215 Views
Online Scheduling on Two Uniform Unbounded Parallel-Batch Machines to Minimize Makespan Jin-Jiang Yuan1
· Li-Li Ren1 · Ji Tian2 · Ru-Yan Fu2
Received: 6 July 2017 / Revised: 13 September 2017 / Accepted: 4 January 2018 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2018
Abstract We study an online (over time) scheduling problem on two uniform unbounded parallel-batch machines with processing speed 1 and v(0 < v 1), respectively, to minimize the makespan. We first show √ that no online algorithm can have a competitive ratio less than 1 + α L , where α L = ( 5 − 1)/2 ≈ 0.618 if 0 < v 1/2, and α L = α2 (v) is the positive root of α 3 +3α 2 +(3−1/v)α−1/v = 0 if 1/2 < v 1. This lower bound is still valid when all jobs have the same processing √ times. Then, √ we provide an online algorithm with a competitive ratio at most min{( 5+1)/2, 2/v}. When the jobs have the same processing times, we present the best possible online algorithm with a competitive ratio 1 + α L .
The first author was supported by the National Natural Science Foundation of China (No. 11671368) and Natural Science Foundation of Henan Province (No. 15IRTSTHN006). Tian was also supported by Natural Science Foundation of Jiangsu Province (No. BK20130169) and the National Natural Science Foundation of China (No. 61573362).
B
Jin-Jiang Yuan [email protected] Li-Li Ren [email protected] Ji Tian [email protected] Ru-Yan Fu [email protected]
1
School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
2
School of Mathematics, China University of Mining and Technology, Xuzhou 221116, Jiangsu, China
123
J.-J. Yuan et al.
Keywords Online scheduling · Uniform parallel-batch machines · Makespan · Competitive ratio Mathematics Subject Classification 90B35 · 90C27
1 Introduction In this paper, online means that jobs arrive online over time, i.e., the information about a job including its processing time is known only at the instant of its arrival. We use competitive ratio to measure the quality of an online algorithm. The competitive ratio R A of an online algorithm A for a minimization scheduling problem is defined by Con (I) , C ∀I opt (I)
R A = sup
where Con (I) and Copt (I) denote the objective value of the schedule produced by algorithm A and the optimal objective value produced by an off-line algorithm for a given job instance I. Parallel-batch scheduling, first introduced by Lee et al. [1], has been extensively studied in the last two decades. In parallel-batch scheduling, a machine can process several jobs as a batch with processing time being defined to be the maximum processing time of jobs in the batch. So, all jobs in a batch have the same starting time and the same completion time in a schedule. There are two versions about parallel-batch scheduling: One is unbounded model with b = ∞; the other is bounded model with b < ∞, where b denotes the capacity of each batch. In this paper, we only consider the
Data Loading...
