Approximation algorithms for bi-objective parallel-machine scheduling in green manufacturing

被引：11

作者：

Jiang, Yiwei ^{[1
]}

Tang, Xuelian ^{[1
]}

Li, Kai ^{[2
,3
]}

Cheng, T. C. E. ^{[4
]}

Ji, Min ^{[1
]}

机构：

[1] Zhejiang Gongshang Univ, Sch Management & E Business, Contemporary Business & Trade Res Ctr, Hangzhou 310018, Peoples R China

[2] Hefei Univ Technol, Sch Management, Hefei 230009, Peoples R China

[3] Minist Educ, Key Lab Proc Optimizat & Intelligent Decis Making, Hefei 230009, Peoples R China

[4] Hong Kong Polytech Univ, Dept Logist & Maritime Studies, Kowloon, Hong Kong, Peoples R China

来源：

COMPUTERS & INDUSTRIAL ENGINEERING | 2023年 / 176卷

基金：

中国国家自然科学基金;

关键词：

Green manufacturing; Parallel-machine scheduling; Approximation algorithm; Worst-case ratio; TARDINESS; OPTIMIZATION;

D O I：

10.1016/j.cie.2022.108949

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We consider bi-objective parallel-machine scheduling in green manufacturing to minimize the makespan and total processing cost. Each machine has a different constant processing cost per unit time. For the objective of minimizing the makespan, given a total cost budget, we provide an approximation algorithm with a worst-case ratio of root 33+1/4 approximate to 1.686, which improves the previous bound of 2. For the objective of minimizing the total processing cost, subject to all the jobs must be completed before a given common deadline, we provide an approximation algorithm with a worst-case ratio of 2+r/3, where r is the ratio of the maximum to the minimum processing cost per unit time on a machine.

引用

页数：8

共 29 条

[1] Production scheduling optimisation with machine state and time-dependent energy costs [J].

Aghelinejad, MohammadMohsen ;

Ouazene, Yassine ;

Yalaoui, Alice .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2018, 56 (16) :5558-5575

[2] Scheduling for sustainable manufacturing: A review [J].

Akbar, Muhammad ;

Irohara, Takashi .

JOURNAL OF CLEANER PRODUCTION, 2018, 205 :866-883

[3] A bi-objective heuristic approach for green identical parallel machine scheduling [J].

Anghinolfi, Davide ;

Paolucci, Massimo ;

Ronco, Roberto .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2021, 289 (02) :416-434

[4] Energy-conscious unrelated parallel machine scheduling under time-of-use electricity tariffs [J].

Che, Ada ;

Zhang, Shibohua ;

Wu, Xueqi .

JOURNAL OF CLEANER PRODUCTION, 2017, 156 :688-697

[5] Energy-efficient bi-objective single-machine scheduling with power-down mechanism [J].

Che, Ada ;

Wu, Xueqi ;

Peng, Jing ;

Yan, Pengyu .

COMPUTERS & OPERATIONS RESEARCH, 2017, 85 :172-183

[6] Scheduling with time-of-use costs [J].

Chen, Bo ;

Zhang, Xiandong .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2019, 274 (03) :900-908

[7] Bi-criteria single-machine batch scheduling with machine on/off switching under time-of-use tariffs [J].

Cheng, Junheng ;

Chu, Feng ;

Liu, Ming ;

Wu, Peng ;

Xia, Weili .

COMPUTERS & INDUSTRIAL ENGINEERING, 2017, 112 :721-734

[8] Bi-criteria formulation for green scheduling with unrelated parallel machines with sequence-dependent setup times [J].

Cota, Luciano P. ;

Coelho, Vitor N. ;

Guimaraes, Frederico G. ;

Souza, Marcone J. F. .

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH, 2021, 28 (02) :996-1017

[9] Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm [J].

Dai, Min ;

Tang, Dunbing ;

Giret, Adriana ;

Salido, Miguel A. ;

Li, W. D. .

ROBOTICS AND COMPUTER-INTEGRATED MANUFACTURING, 2013, 29 (05) :418-429

[10] Parallel Machine Scheduling Under Time-of-Use Electricity Prices: New Models and Optimization Approaches [J].

Ding, Jian-Ya ;

Song, Shiji ;

Zhang, Rui ;

Chiong, Raymond ;

Wu, Cheng .

IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2016, 13 (02) :1138-1154

← 1 2 3 →