Open AccessPareto optimal algorithms for minimizing total (weighted) completion time and maximum cost on a single machine
Author(s) -
Liu Zhi-meng,
Shuguang Li
Publication year - 2022
Publication title -
mathematical biosciences and engineering
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.451
H-Index - 45
eISSN - 1551-0018
pISSN - 1547-1063
DOI - 10.3934/mbe.2022346
Subject(s) - scheduling (production processes) , pareto optimal , single machine scheduling , algorithm , pareto principle , mathematical optimization , mathematics , running time , computer science , combinatorics , job shop scheduling , multi objective optimization , routing (electronic design automation) , computer network
This paper studies the Pareto scheduling problem of minimizing total weighted completion time and maximum cost on a single machine. It is known that the problem is strongly NP-hard. Algorithms with running time $ O(n^3) $ are presented for the following cases: arbitrary processing times, equal release dates and equal weights; equal processing times, arbitrary release dates and equal weights; equal processing times, equal release dates and arbitrary weights.