研究工件带释放时间、送货时间和树层次加工集约束的调度问题。工件的加工开始时间不能早于它的释放时间，送货开始时间等于它的加工完成时间。所有机器形成一个树层次结构：若某机器能加工某工件，则该机器在树上的所有祖先均能加工该工件，这些机器构成该工件的加工集。目标是极小化最大送货完成时间。对于工件释放时间和送货时间任意的一般情形，给出了一个多项式时间近似方案（PTAS）。
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.
