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

Yiwei Jiang, Xuelian Tang, Kai Li, T. C.E. Cheng, Min Ji

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

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 [Formula presented], 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 [Formula presented], where r is the ratio of the maximum to the minimum processing cost per unit time on a machine.

Original languageEnglish
Article number108949
JournalComputers and Industrial Engineering
Volume176
DOIs
Publication statusPublished - Feb 2023

Keywords

  • Approximation algorithm
  • Green manufacturing
  • Parallel-machine scheduling
  • Worst-case ratio

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Fingerprint

Dive into the research topics of 'Approximation algorithms for bi-objective parallel-machine scheduling in green manufacturing'. Together they form a unique fingerprint.

Cite this