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

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.