带树层次加工集约束的调度问题

doi:10.15960/j.cnki.issn.1007-6093.2020.04.009

Abstract

Abstract: 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.

Key words: scheduling, parallel machines, tree-hierarchical processing set restrictions, delivery time, polynomial time approximation scheme

CLC Number:

TP301

ZHANG Yuzhong, LI Shuguang. Scheduling with tree-hierarchical processing set restrictions[J]. Operations Research Transactions, 2020, 24(4): 107-112.

References

[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.

Scheduling with tree-hierarchical processing set restrictions

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	CHEN Feng. Research and application of operations research on intelligent scheduling decision support system for automotive outbound logistics [J]. Operations Research Transactions, 2021, 25(3): 37-73.
[2]	YU Shanshan, JIN Miaomiao, LUO Wenchang. Approximation scheme for rescheduling on a single machine with job delay and rejection [J]. Operations Research Transactions, 2021, 25(2): 104-114.
[3]	SHEN Yindong, QIAN Zhuang, LI Yuanyuan. A survey on driver scheduling in public transportation [J]. Operations Research Transactions, 2021, 25(1): 1-16.
[4]	HUANG Jidan, ZHENG Feifeng, XU Yingfeng, LIU Ming. Parallel machine scheduling with deteriorating installation times in the MapReduce system [J]. Operations Research Transactions, 2020, 24(4): 93-106.
[5]	JIANG Xiaoyan, SHUAI Tianping. Online MapReduce scheduling on two uniform machines [J]. Operations Research Transactions, 2020, 24(3): 57-66.
[6]	LU Shuxiang, Lü Changhong, QIN Tao. An algorithm based on makespan lower bound for quay crane schedule problem in container terminals [J]. Operations Research Transactions, 2020, 24(3): 67-76.
[7]	ZHONG Weiya, SHI Yimei. Robust optimization of rehearsal scheduling under uncertain duration [J]. Operations Research Transactions, 2020, 24(3): 77-86.
[8]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[9]	CHEN Rubing, YUAN Jinjiang. Single-machine scheduling to minimize total weighted late work with positional due-indices [J]. Operations Research Transactions, 2020, 24(2): 131-144.
[10]	LIU Xiaoxia, YU Shanshan, LUO Wenchang. Approximation algorithms for single machine parallelbatch scheduling with release dates subject to the number of rejected jobs not exceeding a given threshold [J]. Operations Research Transactions, 2020, 24(1): 131-139.
[11]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[12]	GOU Yan, DAI Qin, ZHANG Xingong. Scheduling problem with time-and-position-dependent effect on two parallel machines environments [J]. Operations Research Transactions, 2019, 23(4): 86-94.
[13]	LI Ganggang, LU Xiwen. An improved algorithm for single-machine scheduling problem with a period of maintenance to minimize total delivery time [J]. Operations Research Transactions, 2019, 23(4): 95-104.
[14]	LI Wenhua, ZHAI Weina, CHAI Xing, GAO Chao. On-line bounded-batching scheduling of unit-length jobs with two families [J]. Operations Research Transactions, 2019, 23(4): 105-110.
[15]	ZHANG Guochuan, CHEN Lin. The load balancing problem [J]. Operations Research Transactions, 2019, 23(3): 1-14.