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

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

运筹学学报 ›› 2020, Vol. 24 ›› Issue (4): 107-112.doi: 10.15960/j.cnki.issn.1007-6093.2020.04.009

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

张玉忠^1,*, 李曙光²

1. 曲阜师范大学运筹学研究院, 山东日照 276826;
2. 山东工商学院计算机科学与技术学院, 山东烟台 264005

收稿日期:2018-09-15 发布日期:2020-11-18
通讯作者: 张玉忠 E-mail:yuzhongrz@163.com
基金资助:
国家自然科学基金（No.11771251），山东省自然科学基金重点项目（Nos.ZR2015GZ009，ZR201911140724），曲阜师范大学科研项目（No.xkj201504）

Scheduling with tree-hierarchical processing set restrictions

ZHANG Yuzhong^1,*, LI Shuguang²

1. School of Operations Research, Qufu Normal University, Rizhao 276826, Shandong, China;
2. College of Computer Science and Technology, Shandong Technology and Business University, Yantai 264005, Shandong, China

Received:2018-09-15 Published:2020-11-18

摘要/Abstract

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

关键词: 调度, 并行机, 树层次加工集约束, 送货时间, 多项式时间近似方案

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

中图分类号:

TP301

张玉忠, 李曙光. 带树层次加工集约束的调度问题[J]. 运筹学学报, 2020, 24(4): 107-112.

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

参考文献

[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

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 12

编辑推荐

Metrics

本文评价

[1]	陈峰. 运筹学在整车物流智能调度决策支持系统中的研究与应用[J]. 运筹学学报, 2021, 25(3): 37-73.
[2]	沈吟东, 钱壮, 李媛媛. 公共交通驾驶员调度研究综述[J]. 运筹学学报, 2021, 25(1): 1-16.
[3]	黄基诞, 郑斐峰, 徐寅峰, 刘明. 安装时间具有退化效应的MapReduce模型下的平行机调度[J]. 运筹学学报, 2020, 24(4): 93-106.
[4]	陆书翔, 吕长虹, 秦涛. 集装箱码头桥机调度问题基于完工时间下界的算法[J]. 运筹学学报, 2020, 24(3): 67-76.
[5]	仲维亚, 施益媚. 不确定彩排时长下节目调度的鲁棒优化[J]. 运筹学学报, 2020, 24(3): 77-86.
[6]	王翼展, 张安, 陈永, 陈光亭. 堆取料机调度问题的一个近似算法[J]. 运筹学学报, 2020, 24(1): 147-154.
[7]	李英, 乔龙亮, 郑斐峰. 具有预知信息的集装箱码头泊位与岸桥联合调度在线模型[J]. 运筹学学报, 2018, 22(3): 28-36.
[8]	范静, 鲁习文. 机器带不可用时间限制的简单线性恶化供应链排序问题[J]. 运筹学学报, 2016, 20(4): 69-76.
[9]	宁涛, 陈荣, 郭晨, 梁旭. 一种基于双链量子编码的动态车辆路径问题解决策略[J]. 运筹学学报, 2015, 19(2): 72-82.
[10]	段渊. 实时系统中单处理器调度算法的优化设计研究[J]. 运筹学学报, 2013, 17(2): 27-34.
[11]	帅天平，余金果，孙玲. 一种求解延迟工件数最小的混合流水车间调度问题的模拟退火算法[J]. 运筹学学报, 2013, 17(2): 41-47.
[12]	王宏, 林丹, 李敏强. 求解带有时间窗和提前/拖期惩罚的飞机着陆问题的遗传算法[J]. 运筹学学报, 2012, 16(1): 67-76.