The problem of scheduling with release times, delivery times and treehierarchical processing set restrictions is considered. Each job cannot begin processing before its release time, and its delivery begins immediately after processing has been completed. The machines form a tree hierarchical structure:any job requesting a certain machine may be assigned to any of its ancestors in the tree, and the set of these machines is the job's processing set. The objective is to minimize the maximum delivery completion time, i.e., the time by which all jobs are delivered. A polynomial time approximation scheme (PTAS) is presented when the jobs have both unequal release times and unequal delivery times.
[1] Leung Y T, Li C L. Scheduling with processing set restrictions:A literature update[J]. International Journal of Production Economics, 2016, 175(2):1-11.
[2] Graham R L, Lawler E L, Lenstra J K, et al. Optimization and approximation in deterministic sequencing and scheduling:a survey[J]. Annals of Discrete Mathematics, 1979, 5(1):287-326.
[3] Brucker P. Scheduling Algorithms (5th edition)[M]. New York:Springer, 2007.
[4] Bratley P, Florian M, Robillard P. On sequencing with earliest starts and due dates with application to computing bounds for the (n/m/G/F max) problem[J]. Naval Research Logistics Quarterly, 1973, 20(1):57-67.
[5] Hall L A, Shmoys D B. Jackson's rule for single-machine scheduling:making a good heuristic better[J]. Mathematics of Operations Research, 1992, 17:22-35.
[6] Chen B, Potts C N, Woeginger G J. A review of machine scheduling:Complexity, algorithms and approximability[M]//Handbook of Combinatorial Optimization. New York:Springer, 1998:21-169.
[7] Lawler E L, Lenstra J K, Kan A H G R, et al. Sequencing and scheduling:Algorithms and complexity[M]//Handbooks in Operations Research and Management Science, Volume 4:Logistics of Production and Inventory. 1993:445-522.
[8] Papadimitriou C H, Steiglitz K. Combinatorial Optimization:Algorithms and Complexity[M]. New York:Courier Dover Publications, 1998.
[9] Hall L A, Shmoys D B. Approximation schemes for constrained scheduling problems[C]//Proceedings of the 30th Annual IEEE Symposium on Foundations of Computer Science, 1989:134-139.
[10] Mastrolilli M. Efficient approximation schemes for scheduling problems with release dates and delivery times[J]. Journal of Scheduling, 2003, 6(6):521-531.
[11] Barnoy A, Freund A, Naor J. On-line load balancing in a hierarchical server topology[J]. SIAM Journal on Computing, 2001, 31(2):527-549.
[12] Epstein L, Levin A. Scheduling with processing set restrictions:PTAS results for several variants[J]. International Journal of Production Economics, 2011, 133(2):586-595.
[13] Huo Y M, Leung Y T. Fast approximation algorithms for job scheduling with processing set restrictions[J]. Theoretical Computer Science, 2010, 411:3947-3955.
[14] Schwarz U M. A PTAS for scheduling with tree assignment restrictions[J]. arXiv:1009.4529, 2010.
[15] Jackson J R. Scheduling a production line to minimize maximum tardiness[R]. Management Science Research Project, Los Angeles:University of California, 1955.
