可移动周期性维护排序问题的算法研究

doi:10.3785/j.issn.1008-9497.2023.03.007

浙江大学学报（理学版）

2023, Vol. 50

Issue (3): 303-309 DOI: 10.3785/j.issn.1008-9497.2023.03.007

数学与计算机科学

可移动周期性维护排序问题的算法研究

华荣伟¹(

),潘虹¹,严甜海²

^1.杭州医学院，浙江杭州 310053
^2.浙江大学数学科学学院，浙江杭州 310058

Scheduling problem with flexible periodic maintenance activities on two parallel machines

Rongwei HUA¹(

),Hong PAN¹,Tianhai YAN²

^1.Hangzhou Medical College，Hangzhou 310053，China
^2.School of Mathematical Sciences，Zhejiang University，Hangzhou 310058，China

全文: PDF(1033 KB)

HTML( 3 )

摘要：

对于周期性维护的两台同型机排序问题，每台机器在进行时长不超过 $T$ 的加工后需进行时长为 $t$ 的维护，可在两台机器中任选一台加工工件，加工过程不可中断，且不能在维护前后加工同一工件，目标为极小化工件最大完工时间，证明了其不存在最坏情况比小于 $1 + t T$ 的多项式时间近似算法，除非 $P = N P$ 。同时给出了该问题的近似算法，证明了其最坏情况比不超过 $f t T$ 。

关键词： 可移动周期性维护; 最坏情况比; 近似算法

Abstract:

A two parallel machines scheduling problem with flexible periodic maintenance activities is studied. A job selects one of the machines for processing, and the processing is not allowed to be interrupted. The objective is to minimize the makespan, i.e., to maximize the completion time of all jobs, subject to periodic maintenance and non-resumable jobs, which means that the job can't be processed before or after the periodic maintenance. We show that there is no polynomial time approximation algorithm with a worst-case ration less than $1 + t T$ unless $P = N P$ . An approximation algorithm with the worst-case performance ration of $f t T$ is also provided.

Key words: flexible periodic maintenance worst-case performance ration approximation algorithm

收稿日期: 2022-04-21 出版日期: 2023-05-19

CLC:

O 226

作者简介: 华荣伟（1966—），ORCID：https：//orcid.org/0000-0002-3220-7546，男，硕士，副教授，主要从事组合优化研究，E-mail：397078312@qq.com.

	服务
	把本文推荐给朋友
	加入引用管理器
	E-mail Alert
	RSS
	作者相关文章
	华荣伟
	潘虹
	严甜海

引用本文:

华荣伟, 潘虹, 严甜海. 可移动周期性维护排序问题的算法研究[J]. 浙江大学学报（理学版）, 2023, 50(3): 303-309.

Rongwei HUA, Hong PAN, Tianhai YAN. Scheduling problem with flexible periodic maintenance activities on two parallel machines. Journal of Zhejiang University (Science Edition), 2023, 50(3): 303-309.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2023.03.007 或 https://www.zjujournals.com/sci/CN/Y2023/V50/I3/303

图1 需周期性维护且维护时段可移动的两台同型机

图2 函数f0(β)的图

1	ADIRI I， BRUNO J， FROSTIG E， et al. Single machine flow-time scheduling with a single breakdown［J］. Acta Informatica，1989， 26（7）： 679-696. DOI：10.1007/BF00288977 doi: 10.1007/BF00288977
2	LEE C Y. Machine scheduling with an availability constraints［J］. Journal of Global Optimization， 1996， 9：363-384. DOI：10.1007/BF00121681 doi: 10.1007/BF00121681
3	LEE C Y， LEI L， PINEDO M. Current trends in deterministic scheduling［J］. Annals of Operations Research， 1997， 70：1-41. DOI：10.1023/A：1018909801944 doi: 10.1023/A：1018909801944
4	MA Y， CHU C B， ZUO C R. A survey of scheduling with deterministic machine availability constraints［J］. Computers & Industrial Engineering， 2010， 58（2）：199-211. DOI：10.1016/j.cie.2009.04.014 doi: 10.1016/j.cie.2009.04.014
5	SCHMIDT G. Scheduling with limited machine availability［J］. European Journal of Operational Research， 2000， 121（1）： 1-15. DOI：10.1016/S0377-2217（98）00367-1 doi: 10.1016/S0377-2217（98）00367-1
6	JI M， HE Y， CHENG T C E. Single-machine scheduling with periodic maintenance to minimize makespan［J］. Computers & Operations Research， 2007， 34（6）： 1764-1770. DOI：10.1016/j.cor.2005. 05.034 doi: 10.1016/j.cor.2005. 05.034
7	QI X T， CHEN T， TU F. Scheduling the maintenance on a single machine［J］. Journal of the Operational Society，1999， 50：1071-1078. DOI：10.1057/palgrave.jors.2600791 doi: 10.1057/palgrave.jors.2600791
8	CHEN J S. Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan［J］. European Journal of Operational Research， 2008， 190（1）：90-102. DOI：10.1016/j.ejor.2007.06.029 doi: 10.1016/j.ejor.2007.06.029
9	DIEDRICH F， JANSEN K， PASCUAL F， et al. Approximation algorithms for scheduling with reservations［J］. Algorithmica， 2010， 58（2）：391-404. DOI：10.1007/s00453-008-9271-2 doi: 10.1007/s00453-008-9271-2
10	YU X Y， ZHANG Y L， STEINER G. Single-machine scheduling with periodic maintenance to minimize makespan revisited［J］. Journal of Scheduling， 2014， 17（3）： 263-270. DOI：10.1007/s10951-013-0350-0 doi: 10.1007/s10951-013-0350-0
11	QI X T. A note on worst-case performance of heuristics for maintenance scheduling problems［J］. Discrete Applied Mathematics， 2007， 155（3）： 416-422. DOI：10.1016/j.dam.2006.06.005 doi: 10.1016/j.dam.2006.06.005
12	XU D H， YIN Y Q， LI H X. A note on "scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan"［J］. European Journal of Operational Research， 2009， 197（2）：825-827. DOI：10.1016/j.ejor.2008.07.021 doi: 10.1016/j.ejor.2008.07.021
13	XU D H， CHENG Z M， YIN Y Q， et al. Makespan minimization for two parallel machines scheduling with a periodic availability constraint［J］. Computers & Operations Research， 2009， 36（6）：1809-1812. DOI：10.1016/j.cor.2008.05.001 doi: 10.1016/j.cor.2008.05.001
14	LI G G， LU X W. Two-machine scheduling with periodic availability constraints to minimize makespan［J］. Journal of Industrial & Management Optimization， 2017， 11（2）：685-700. DOI：10.3934/jimo.2015.11.685 doi: 10.3934/jimo.2015.11.685
15	SUN K B， LI H X. Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines［J］. International Journal of Production Economics， 2010， 124（1）： 151-158. DOI：10.1016/j.ijpe.2009.10.018 doi: 10.1016/j.ijpe.2009.10.018
16	XU D H， SUN K B， LI H X. Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan［J］. Computers & Operations Research， 2008， 35（4）： 1344-1349. DOI：10.1016/j.cor.2006.08.015 doi: 10.1016/j.cor.2006.08.015
17	LIU M， ZHENG F F， CHU C B， et al. Optimal algorithms for online scheduling on parallel machines to minimize the makespan with a periodic availability constraint［J］. Theoretical Computer Science， 2011， 412（39）：5225-5231. DOI：10.1016/j.tcs.2011.05.028 doi: 10.1016/j.tcs.2011.05.028
18	谈之奕，林凌. 组合优化与博弈论［M］. 杭州：浙江大学出版社， 2015. TAN Z Y， LIN L. Combinatorial Optimization and Game Theory［M］. Hangzhou：Zhejiang University Press， 2015.
19	GYORGY D. The tight bound of first fit decreasing bin-packing algorithm is FFD（I）=（11/9）OPT（I）+ 6/9［J］. Lecture Notes in Computer Science， 2007，4614： 1-11. DOI：10.1007/978-3-540-74450-4_1 doi: 10.1007/978-3-540-74450-4_1
20	SAHNI S K. Algorithms for scheduling independent tasks［J］. Journal of the ACM， 1976，23（1）：116-127. DOI：10.1145/321921.321934 doi: 10.1145/321921.321934

[1]	沈灏. 底为正方形的三维装箱问题[J]. 浙江大学学报（理学版）, 1999, 26(3): 44-51.
[2]	陈光亭，张国川. 约束最小生成树问题研究[J]. 浙江大学学报（理学版）, 1999, 26(2): 28-32.

Viewed

Full text

Abstract

Cited

Shared

Discussed