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 条

[11] Parallel-machine scheduling to minimize tardiness penalty and power cost [J].

Fang, Kuei-Tang ;

Lin, Bertrand M. T. .

COMPUTERS & INDUSTRIAL ENGINEERING, 2013, 64 (01) :224-234

[12] Uniform parallel machine scheduling with fuzzy processing times under resource consumption constraint [J].

Li, Kai ;

Chen, Jianfu ;

Fu, Hong ;

Jia, Zhaohong ;

Fu, Weizhong .

APPLIED SOFT COMPUTING, 2019, 82

[13]

[李凯 Li Kai], 2019, [系统工程理论与实践, Systems Engineering-Theory & Practice], V39, P165

[14] Minimizing total tardiness on two uniform parallel machines considering a cost constraint [J].

Li, Kai ;

Xiao, Wei ;

Yang, Shanlin .

EXPERT SYSTEMS WITH APPLICATIONS, 2019, 123 :143-153

[15] Uniform parallel machine scheduling problems with fixed machine cost [J].

Li, Kai ;

Zhang, Hui-Juan ;

Cheng, Ba-Yi ;

Pardalos, Panos M. .

OPTIMIZATION LETTERS, 2018, 12 (01) :73-86

[16] Parallel machine scheduling problems in green manufacturing industry [J].

Li, Kai ;

Zhang, Xun ;

Leung, Joseph Y. -T. ;

Yang, Shan-Lin .

JOURNAL OF MANUFACTURING SYSTEMS, 2016, 38 :98-106

[17] Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency [J].

Moon, Joon-Yung ;

Shin, Kitae ;

Park, Jinwoo .

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY, 2013, 68 (1-4) :523-535

[18] Minimizing total carbon footprint and total late work criterion in flexible job shop scheduling by using an improved multi-objective genetic algorithm [J].

Piroozfard, Hamed ;

Wong, Kuan Yew ;

Wong, Wai Peng .

RESOURCES CONSERVATION AND RECYCLING, 2018, 128 :267-283

[19] Green permutation flowshop scheduling problem with sequence-dependent setup times: a case study [J].

Ramezanian, Reza ;

Vali-Siar, Mohammad Mahdi ;

Jalalian, Mahdi .

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2019, 57 (10) :3311-3333

[20] Bi-objective green scheduling in uniform parallel machine environments [J].

Safarzadeh, Hamid ;

Niaki, Seyed Taghi Akhavan .

JOURNAL OF CLEANER PRODUCTION, 2019, 217 :559-572

← 1 2 3 →