A tabu search algorithm for the unrelated parallel machine scheduling problem with varied carbon emission constraints in different time intervals
研究了不同时间段具有变化碳排放约束的不相关并行机调度问题，提出混合整数线性规划模型和禁忌搜索算法，以最小化最大完工时间，并通过随机实例验证了模型和算法的有效性。
The carbon emissions generated during the rapid development of the manufacturing industry have caused severe environmental pollution. Research on parallel machine scheduling problems considering carbon emission constraints has started to emerge in recent years to promote sustainable development and achieve low carbon emissions in production. In this paper, we consider an unrelated parallel machine scheduling problem with various carbon emission constraints in different time intervals. A mixed integer linear programming model with the objective of minimising the makespan is formulated to describe the problem accurately. Since the high complexity of our problem, we propose an efficient tabu search algorithm with a dedicated linked list structure to address this problem. Firstly, we generate four initial sequences according to the proposed heuristic rules and apply a greedy insertion decoding method to obtain the scheduling scheme. Then, we employ the 2-swap neighbourhood search strategy to exploit the promising solution space. The proposed model and algorithm are tested on extensive instances generated randomly. Computational results validate the correctness of the model and the effectiveness of the tabu search algorithm.