Note on the time complexity of resource constrained scheduling with general truncated job-dependent learning effect
- PDF / 239,378 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 84 Downloads / 194 Views
Note on the time complexity of resource constrained scheduling with general truncated job-dependent learning effect Dexin Zou1,2 · Chong Jiang3 · Weiwei Liu4
© Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract In a recent paper (He et al. in J Comb Optim 33(2):626–644, 2017), the authors considered single machine resource allocation scheduling with general truncated jobdependent learning effect. For the convex resource consumption function and limited resource cost, the problem is to minimize the weighted sum of makespan, total completion time, the total absolute deviation in completion time and resource consumption cost. They conjectured that this problem is NP-hard. In this note we show that this problem can be solved in O(n 3 ) time. It is also shown that Lemma 4 in He et al. (2017) is incorrect by a counter-example. Keywords Scheduling · Learning effect · Resource allocation · Time complexity
1 Introduction We study the scheduling problem with general truncated job-dependent learning effect and convex resource allocation. Following the assumptions and notation given in He et al. (2017), we have a set of n independent jobs {J1 , J2 , . . . , Jn } to be processed on a single machine. The job preemption is not allowed, and the actual processing time
B
Chong Jiang [email protected]
1
Institute of Sports Development and Planning, Nanjing Sport Institute, Nanjing 210014, People’s Republic of China
2
Jiangsu Sports and Health Engineering Collaborative Innovation Center, Nanjing 210014, Jiangsu, People’s Republic of China
3
Department of Sport Education and Humanity, Nanjing Sport Institute, Nanjing 210014, People’s Republic of China
4
Department of Basic, Shenyang Sport University, Shenyang 110102, People’s Republic of China
123
Journal of Combinatorial Optimization
of job J j scheduled in position r is p Aj
=
k w j max f j (r ), a j , u j > 0, uj
(1)
where w j is a workload time of job J j (Shabtay and Steiner 2007), k is a positive constant, a j is a truncation parameter of job J j (0 < a j < 1), and u j is the amount of resource that can be allocated to job J j . For a given schedule π = (J1 , J2 , . . . , Jn ), let C j = C j (π ) be the completion n time of job J j . Let Cmax = max{C j | j = 1, 2, . . . , n} be the makespan, T C = j=1 C j be the total completion time, and T ADC = n n |C − C | be the total absolute deviation in completion time. We want to j i i=1 j=i determine the job schedule π , and the resource allocations u = (u 1 , u 2 , . . . , u n ) such that Z (π, u) = αCmax + βTC + γ TADC + δ nj=1 v j u j is minimized, where weights α, β, γ and δ are given non-negative constants and v j is the cost of allocating one unit of resource to J j . Using the three-field notation scheme (Graham et al. 1979; Shabtay and Steiner 2007; Biskup 2008; Azzouz et al. 2017; Geng et al. 2019), we denote w j max{ f j (r ),a j } k n , j=1 v j u j ≤ U |αCmax + the problem under study as 1| p Aj = uj βTC + γ TADC + δ nj=1 v j u j . w j max{ f j (r ),a j } k H
Data Loading...
