A tabu search algorithm for the unrelated parallel machine scheduling problem with varied carbon emission constraints in different time intervals

Abstract

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.

Keywords:

• Unrelated parallel machine
• carbon emission
• makespan
• tabu search algorithm

Acknowledgements

We thank the anonymous referees for their constructive criticisms and helpful comments. We also express our gratitude to the editors for their valuable advice.

Data availability statement

The data and source codes supporting the findings of this study are available from the corresponding author.

Disclosure statement

We have no competing interests.

Additional information

Funding

We acknowledge the support of the National Natural Science Foundation of China (Grant No.71671139).