Scheduling Jobs with Release and Delivery Times Subject to Nested Eligibility Constraints
- PDF / 380,563 Bytes
- 15 Pages / 439.37 x 666.142 pts Page_size
- 57 Downloads / 166 Views
Scheduling Jobs with Release and Delivery Times Subject to Nested Eligibility Constraints Yu-Zhong Zhang1 · Shu-Guang Li2,3 Received: 23 August 2018 / Revised: 12 December 2018 / Accepted: 10 September 2019 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract The problem of scheduling jobs with release and delivery time subject to machine eligibility constraints is considered. The eligible sets of the jobs are nested, and preemptions are not allowed. The goal is to minimize the maximum delivery completion time, i.e., the time by which all jobs are delivered. For the special case of equal release time, a 2-approximation algorithm is presented whose running time depends linearly on the number of jobs. For the general case of unequal release time, a polynomial time approximation scheme is derived. Keywords Scheduling · Nested eligibility constraints · Release time · Delivery time · Polynomial time approximation scheme Mathematics Subject Classification 90B35 · 68M20
This work was supported by the National Natural Science Foundation of China (No. 11771251), Key project of Shandong Provincial Natural Science Foundation of China (No. ZR2015GZ009), Shandong Provincial Education Reform Project (No. 2015M098).
B
Yu-Zhong Zhang [email protected] Shu-Guang Li [email protected]
1
Institute of Operations Research, Qufu Normal University, Rizhao 276826, Shandong, China
2
Key Laboratory of Intelligent Information Processing in Universities of Shandong (Shandong Institute of Business and Technology), Yantai 264005, Shandong, China
3
College of Computer Science and Technology, Shandong Institute of Business and Technology, Yantai 264005, Shandong, China
123
Y. Zhang, S. Li
1 Introduction The problem of scheduling jobs with release and delivery time subject to nested eligibility constraints is defined as follows. There are a set of n independent jobs J {1, 2, · · · , n} and a set of m parallel machines M {M1 , M2 , · · · , Mm }. The machines are not identical; they operate at the same speed but differ in their functionality. Each job j has to be processed without interruption for p j units of time (called its processing time) by a machine that belongs to a specific subset M j of the m machines called its eligible set and cannot be processed before its release time r j . After completing its processing, job j requires q j units of time (called its delivery time) which can be interpreted as the transportation time to the customer. If S j denotes the start time of job j in a schedule, then its delivery completion time is defined as D j S j + p j + q j . The eligible sets of the jobs are nested, i.e., for any two jobs j1 and j2 , either M j1 ∩ M j2 ∅ or M j1 ⊆ M j2 or M j2 ⊆ M j1 . The objective is to find a feasible schedule so as to minimize the time by which all jobs are delivered, i.e., the maximum delivery completion time, Dmax max j D j . In the notation of Graham et al. [1], this problem is
Data Loading...
