考虑碳排放成本的计件维护单机调度问题

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

运筹学学报（中英文） ›› 2025, Vol. 29 ›› Issue (2): 68-79.doi: 10.15960/j.cnki.issn.1007-6093.2025.02.005

考虑碳排放成本的计件维护单机调度问题

郭思琦¹, 周萍², 蒋义伟¹, 季敏¹^,*()

1. 浙江工商大学管理工程与电子商务学院, 浙江杭州 310018
2. 浙江商业职业技术学院人文学院, 浙江杭州 310053

收稿日期:2022-02-21 出版日期:2025-06-15 发布日期:2025-06-12
通讯作者: 季敏 E-mail:jimkeen@163.com
基金资助:
国家自然科学基金(11971434);国家自然科学基金(11871327);浙江省自然科学基金重点项目(LZ23G010001)

Single-machine scheduling with carbon emission cost and piece-rate maintenance

Siqi GUO¹, Ping ZHOU², Yiwei JIANG¹, Min JI¹^,*()

1. School of Management and E-Business, Zhejiang Gongshang University, Hangzhou 310018, Zhejiang, China
2. College of Humanities, Zhejiang Business College, Hangzhou 310053, Zhejiang, China

Received:2022-02-21 Online:2025-06-15 Published:2025-06-12
Contact: Min JI E-mail:jimkeen@163.com

摘要/Abstract

摘要：

研究带有碳排放成本和计件维护情形的单机调度问题。每完成若干个工件需进行一次维护活动, 机器在加工工件和维护活动时会产生相应的碳排放量。分别针对极小化最大完工时间和总完工时间两个目标函数, 建立了极小化加工成本和碳排放成本之和的调度模型。证明了该问题可转化为指派问题并给出了时间复杂度为$O(n^4)$的多项式时间算法。

关键词: 碳排放, 计件维护, 调度, 多项式时间算法

Abstract:

This paper considers single machine scheduling with carbon emission cost and piece rate maintenance. A maintenance activity is required after processing a number of jobs. During the processing of jobs and maintenance activities, the corresponding carbon emissions will be generated. For both minimizing the maximum completion time and total completion time, we establish a scheduling model of minimizing the total cost of processing and carbon emission, respectively. It is shown that this problem can be transformed into an assignment problem and a polynomial time algorithm with time complexity of $O(n^4)$ is given.

Key words: carbon emission, piece-rate maintenance, scheduling, polynomial time algorithm

中图分类号:

O221.2

郭思琦, 周萍, 蒋义伟, 季敏. 考虑碳排放成本的计件维护单机调度问题[J]. 运筹学学报（中英文）, 2025, 29(2): 68-79.

Siqi GUO, Ping ZHOU, Yiwei JIANG, Min JI. Single-machine scheduling with carbon emission cost and piece-rate maintenance[J]. Operations Research Transactions, 2025, 29(2): 68-79.

图/表 4

图1

表1

表2

表3

参考文献 13

1	李刚刚, 鲁习文. 目标为最小化工件运输时间和单台机器带一个维修时间段的排序问题的一个改进算法[J]. 运筹学学报, 2019, 23 (4): 95- 104. doi: 10.15960/j.cnki.issn.1007-6093.2019.04.008
2	Mosheiov G , Oron D . Due-date assignment and maintenance activity scheduling problem[J]. Mathematical and Computer Modelling, 2006, 44 (11): 1053- 1057.
3	蒋志高. 考虑多阶段维护且加工时间可变的车间作业调度问题研究[D]. 上海: 上海交通大学, 2011: 19-52.
4	Ji M , Cheng T C E . Parallel-machine scheduling with simple linear deterioration to minimize total completion time[J]. European Journal of Operational Research, 2007, 188 (2): 343- 347.
5	虞先玉, 游运, 温荣生. 带有工件实际加工时间上界的调度问题研究[J]. 东华理工大学学报(自然科学版), 2012, 35 (4): 443- 448.
6	Yu X Y , Zhang Y L , Huang K . Multi-machine scheduling with general position-based deterioration to minimize total load revisited[J]. Information Processing Letters, 2014, 114 (8): 399- 404. doi: 10.1016/j.ipl.2014.02.009
7	Yu X Y , Zhang Y L . Single machine scheduling with aging effect and upper-bounded actual processing times[J]. Arabian Journal for Science and Engineering, 2014, 39 (2): 1489- 1495. doi: 10.1007/s13369-013-0716-9
8	杨幸博, 罗国富, 宋俊杰, 等. 多目标柔性作业车间低碳调度研究[J]. 轻工学报, 2020, 35 (6): 93- 99.
9	王彤. 低碳经济下考虑配送时间需求的生产调度优化研究[D]. 重庆: 重庆大学, 2019: 1-30.
10	黄逸文, 黄文焘, 卫卫, 等. 大型海港综合能源系统物流-能量协同优化调度方法[J]. 中国电机工程学报, 2022, 1- 12.
11	董君, 叶春明. 具有学习效应的半导体晶圆制造绿色车间调度问题研究[J]. 运筹与管理, 2021, 30 (4): 217- 223.
12	文笑雨, 王康红, 李浩, 等. 不确定扰动下带有缓冲区的作业车间调度仿真与优化[J]. 轻工学报, 2020, 35 (6): 84- 92.
13	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, 287- 326.

工件$ j $	$ J_1 $	$ J_2 $	$ J_3 $	$ J_4 $	$ J_5 $	$ J_6 $
基本加工时间$ p_j $	12	15	26	11	8	16
碳排放当量$ \chi $	5.52	-	-	-	-	-
加工活动的设备功率$ I_1 $	26	-	-	-	-	-
维护活动的设备功率$ I_2 $	10	-	-	-	-	-
$ w $	0.5	-	-	-	-	-
$ q $	0.8	-	-	-	-	-
单位制造期成本$ \mu $	2.6	-	-	-	-	-
单位加工时间成本$ \gamma $	3.2	-	-	-	-	-
单位碳排放成本$ \theta $	1.2	-	-	-	-	-

$ h $的取值	最优工件排序	$ TC_z $
1	$ (J_6, J_4, J_2, J_1, J_5, J_3) $	20 449.90
2	$ (J_6, J_4, J_2, J_5, J_3, J_1) $	21 918.90
3	$ (J_6, J_4, J_5, J_3, J_2, J_1) $	23 099.31
4	$ (J_6, J_1, J_4, J_5, J_3, J_2) $	24 966.20
5	$ (J_6, J_2, J_1, J_4, J_5, J_3) $	28 522.50

$ h $的取值	最优工件排序	$ TC_w $
1	$ (J_5, J_4, J_1, J_2, J_6, J_3) $	21 414.80
2	$ (J_5, J_4, J_1, J_2, J_6, J_3) $	19 724.10
3	$ (J_5, J_4, J_1, J_2, J_6, J_3) $	18 452.21
4	$ (J_5, J_4, J_1, J_2, J_6, J_3) $	18 444.37
5	$ (J_5, J_4, J_1, J_2, J_6, J_3) $	18 357.65

[1]	袁园, 兰艳, 韩鑫. 带有维护窗口的调度问题的综述[J]. 运筹学学报（中英文）, 2025, 29(1): 1-18.
[2]	李娜, 马冉, 李龙, 张玉忠. 具有学习效应的预制构件生产调度研究[J]. 运筹学学报（中英文）, 2025, 29(1): 19-30.
[3]	徐博, 马卫民, 柯华, 张浩. 基于秩2矩阵近似的飞机起降多目标调度模型与算法研究[J]. 运筹学学报（中英文）, 2024, 28(4): 29-43.
[4]	葛晴, 录岭法, 原晋江, 张利齐. 单机上一个与总完工时间及最大完工时间相关的工件可拒绝的ND双代理排序问题[J]. 运筹学学报（中英文）, 2024, 28(4): 66-74.
[5]	吴琼, 王长军. 基于拉格朗日松弛的产能共享讨价还价研究[J]. 运筹学学报（中英文）, 2024, 28(2): 93-102.
[6]	杨子兰, 朱娟萍, 杨宇. 有向网络中最大容量支撑树形图扩容问题[J]. 运筹学学报（中英文）, 2024, 28(2): 151-158.
[7]	何胜学. 基于超级时空网络的公交车辆调度模型及3M进化算法[J]. 运筹学学报, 2023, 27(3): 68-82.
[8]	徐薇, 黄悦丰, 陈彩华. 考虑配置储能系统的电动公交充电站充放电调度策略[J]. 运筹学学报, 2023, 27(2): 95-109.
[9]	于静, 徐哲, 谢芳. 带有活动重叠的项目调度问题新算法: 分支定界法[J]. 运筹学学报, 2023, 27(1): 115-126.
[10]	万龙, 黄晓莉, 梅嘉杰. PDD规则下最小化最大延误调度问题[J]. 运筹学学报, 2022, 26(4): 75-86.
[11]	张斌武, 关秀翠. 单位无穷范数下边权有界的最小支撑树逆最优值问题[J]. 运筹学学报, 2022, 26(3): 44-56.
[12]	苏兵, WyattCarlson, 范佳彬, GAO Arthur, 邵艳君, 林国辉. 最小化碳排放的共享单车迁移问题[J]. 运筹学学报, 2022, 26(3): 75-91.
[13]	王银玲, 韩鑫, 邵欣欣. 关于带运输的单机调度在线问题的研究[J]. 运筹学学报, 2022, 26(1): 125-133.
[14]	徐晨, 徐寅峰, 郑斐峰. 考虑部分工件不可打扰的多任务调度问题研究[J]. 运筹学学报, 2021, 25(4): 91-100.
[15]	陈峰. 运筹学在整车物流智能调度决策支持系统中的研究与应用[J]. 运筹学学报, 2021, 25(3): 37-73.

考虑碳排放成本的计件维护单机调度问题

Single-machine scheduling with carbon emission cost and piece-rate maintenance

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 4

参考文献 13

相关文章 15

编辑推荐

Metrics

本文评价