关键词: 碳交易, 项目调度, 马尔可夫决策过程, 深度强化学习

Abstract: Heavy machinery used in construction projects generates significant carbon emissions. The carbon trading scheme aims to reduce these emissions through market mechanism. This paper proposes a Project Scheduling Problem with a Limited Construction Site in a Carbon Trading Scheme (PSPLCS-CTS). The objective is to minimize the total project cost, including the carbon trading cost. We assume construction machinery can operate at different speeds, leading to varying carbon emissions and activity durations. Upon project completion, if actual carbon emissions exceed the allocated quota, the excess emissions must be purchased additionally; conversely, any surplus quota can be sold.
Based on the above analysis, we construct an integer programming model for PSPLCS-CTS. Then, the integer programming model is transformed into a Markov Decision Process (MDP) model. We design five key components of the MDP model according to the problem’s characteristics: decision points, states, actions, state transition equations and reward function.
We develop a two-stage algorithm (Double DQN-LS) that combines Double Deep Q-Network and local search to solve the MDP model. In the first stage, the agent interacts with the environment to generate experiences, which are stored in a replay buffer and then randomly sampled for training. The state and action information are converted into a matrix and input to the network, where convolutional layers automatically extract features, and the Q-value of the state-action pair is estimated. In addition, to reduce the overestimation of the target value, the evaluation network is used to select the action during the learning process, and the target network is used to estimate its Q-value to improve the stability and performance of the algorithm. In the second stage, two local search algorithms are employed to enhance the quality of the schedule produced by the Double DQN.
Finally, extensive computational experiments are conducted to verify the effectiveness of the algorithm. For each set of instances, a sample is randomly selected for training at the level of each characteristic parameter. The trained Double DQN is then used to solve other new instances, and the two local search algorithms are used to refine the schedules generated by the Double DQN. The experimental results show the proposed Double DQN-LS algorithm outperforms the Genetic Algorithm (GA) and Estimation of Distribution Algorithm (EDA) on instances with larger sizes. Furthermore, the Double DQN-LS algorithm demonstrates a significant advantage in solving efficiency on all instances, with an average solving time of only about 6% of that of GA and 12% of that of EDA.

Key words: carbon trading, project scheduling, Markov decision processes, deep reinforcement learning