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

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

Abstract

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

CLC Number:

O221.2

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.

Figures/Tables 4

References 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]	ZHAO Di, YU Jin, LU Xiwen. Approximation algorithms for two-agent serial batching scheduling problems [J]. Operations Research Transactions, 2025, 29(2): 184-193.
[2]	Yuan YUAN, Yan LAN, Xin HAN. A survey of scheduling with maintenance periods [J]. Operations Research Transactions, 2025, 29(1): 1-18.
[3]	Na LI, Ran MA, Long LI, Yuzhong ZHANG. Study on the production scheduling of prefabricated components with learning effect [J]. Operations Research Transactions, 2025, 29(1): 19-30.
[4]	Tongxin CUI, Qian XIA, Xingong ZHANG. Single two-agent scheduling problems with slack due date to minimize the total weighted tardiness [J]. Operations Research Transactions, 2025, 29(1): 31-40.
[5]	Shipian DU, Manzhan GU. Stochastic scheduling to minimize the expected total number of tardy jobs with machine maintenance activities [J]. Operations Research Transactions, 2025, 29(1): 142-158.
[6]	Wenjie LI, Zhihui DU, Menglong SU. Research on the NDP-constraint online scheduling of jobs have agreeable processing times and delivery times [J]. Operations Research Transactions, 2024, 28(4): 18-28.
[7]	Bo XU, Weimin MA, Hua KE, Hao ZHANG. Research on the multi-objective model and algorithm for aircraft takeoff/landing scheduling based on rank 2 matrix approximation [J]. Operations Research Transactions, 2024, 28(4): 29-43.
[8]	Qing GE, Lingfa LU, Jinjiang YUAN, Liqi ZHANG. An ND two-agent scheduling problem with rejection on a single machine related to the total completion time and makespan [J]. Operations Research Transactions, 2024, 28(4): 66-74.
[9]	Chengwen JIAO. Online scheduling on a single parallel-batch machine with linear lookahead [J]. Operations Research Transactions, 2024, 28(4): 111-116.
[10]	Juannian XU, Ran MA, Wenwen HAN, Yuzhong ZHANG. Single-machine online scheduling to minimize maximum weighted completion time with limited weights [J]. Operations Research Transactions, 2024, 28(2): 71-80.
[11]	Qiiong WU, Changjun WANG. Production capacity sharing bargaining based on Lagrangian relaxation [J]. Operations Research Transactions, 2024, 28(2): 93-102.
[12]	Zilan YANG, Juanping ZHU, Yu YANG. The expansion problem of maximum capacity spanning arborescence in networks [J]. Operations Research Transactions, 2024, 28(2): 151-158.
[13]	Shengxue HE. Transit vehicle scheduling model and 3M evolutionary algorithm based on super spatiotemporal network [J]. Operations Research Transactions, 2023, 27(3): 68-82.
[14]	Jie GAO, Juan ZOU, Yukang SUI, Yuzhong ZHANG. Unrelated parallel-machine scheduling with deteriorating maintenance activities and job rejection [J]. Operations Research Transactions, 2023, 27(3): 137-149.
[15]	Wei XU, Yuefeng HUANG, Caihua CHEN. Charging and discharging scheduling for electric bus charging station with energy storage system [J]. Operations Research Transactions, 2023, 27(2): 95-109.

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

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 4

References 13

Related Articles 15

Recommended Articles

Metrics

Comments