工件具有子工件工期的排序问题

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

Abstract

Abstract: In this paper, we study a single machine scheduling problem in which sub-jobs have due dates. Given a set of jobs, each job is divided into several sub-jobs and each sub-job has a due date. A job is completed on time only if all its sub-jobs are completed before their due dates. We prove that even if each job has two sub-jobs, this problem is NP-hard and there is no FPTAS for this special case. Furthermore, we propose two heuristics for this model and a heuristic to get an upper bound and carry out numerical experiments to compare their performances.

Key words: scheduling, sub-job's due date, heuristic algorithm

CLC Number:

O223

ZHONG Weiya, YANG Ruoyao. Scheduling with sub-jobs' due dates[J]. Operations Research Transactions, 2019, 23(2): 67-74.

References 9

[1]	Moore J M. An job, one machine sequencing algorithm for minimizing the number of late jobs[J]. Management Science, 1968, 15:102-109.
[2]	Lenstra J K, Kan Rinnooy A H G, Brucker P. Complexity of machine scheduling problems[J]. Annals of Discrete Mathematics, 1977, 1:343-362.
[3]	Stéphane D P, Sevaux M. An exact method to minimize the number of tardy jobs in single machine scheduling[J]. Journal of Scheduling, 2004, 7:405-420.
[4]	Chen B, Potts C N, Strusevich V A. Approximation algorithms for two-machine flow shop scheduling with batch setup times[J]. Mathematical Programming, 1998, 82:255-271.
[5]	Gong H, Tang L, Leung J Y T. Parallel machine scheduling with batch deliveries to minimize total flow time and delivery cost[J]. Naval Research Logistics, 2016, 63:492-502.
[6]	Liu L L, Ng C T, Cheng T C E. On the complexity of bi-criteria scheduling on a single batch processing machine[J]. Journal of Scheduling, 2010, 13, 629-638.
[7]	Liu Z, Yuan J, Cheng T C E. On scheduling an unbounded batch machine[J]. Operations Research Letters, 2003, 31, 42-48.
[8]	Garey M R, Johnson D S. Computers and Intractability:A Guide to the Theory of NPCompleteness[M]. New York:Freeman, 1979.
[9]	Woeginger G J. When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)?[J]. Informs Journal on Computing, 2000, 12:57-74.

[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]	ZHANG Yuzhong, LI Shuguang. Scheduling with tree-hierarchical processing set restrictions [J]. Operations Research Transactions, 2020, 24(4): 107-112.
[6]	JIANG Xiaoyan, SHUAI Tianping. Online MapReduce scheduling on two uniform machines [J]. Operations Research Transactions, 2020, 24(3): 57-66.
[7]	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.
[8]	ZHONG Weiya, SHI Yimei. Robust optimization of rehearsal scheduling under uncertain duration [J]. Operations Research Transactions, 2020, 24(3): 77-86.
[9]	ZHANG Yuzhong. A survey on job scheduling with rejection [J]. Operations Research Transactions, 2020, 24(2): 111-130.
[10]	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.
[11]	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.
[12]	WANG Yizhan, ZHANG An, CHEN Yong, CHEN Guangting. An approximation algorithm for reclaimer scheduling [J]. Operations Research Transactions, 2020, 24(1): 147-154.
[13]	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.
[14]	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.
[15]	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.

Scheduling with sub-jobs' due dates

PDF

Knowledge

Abstract

Cite this article

share this article

References 9

Related Articles 15

Recommended Articles

Metrics

Comments