Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works | Zendy

Shuen Guo | Zendy; Zhichao Geng | Zendy; Jinjiang Yuan | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Single-machine Pareto-scheduling with multiple weighting vectors for minimizing the total weighted late works

Author(s) -

Shuen Guo,

Zhichao Geng,

Jinjiang Yuan

Publication year - 2021

Publication title -

journal of industrial and management optimization

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.325

H-Index - 32

eISSN - 1553-166X

pISSN - 1547-5816

DOI - 10.3934/jimo.2021192

Subject(s) - weighting , unary operation , pareto principle , mathematical optimization , time complexity , computer science , polynomial time approximation scheme , scheduling (production processes) , mathematics , algorithm , combinatorics , medicine , radiology

In this paper, we study the single-machine Pareto-scheduling of jobs with multiple weighting vectors for minimizing the total weighted late works. Each weighting vector has its corresponding weighted late work. The goal of the problem is to find the Pareto-frontier for the weighted late works of the multiple weighting vectors. When the number of weighting vectors is arbitrary, it is implied in the literature that the problem is unary NP-hard. Then we concentrate on our research under the assumption that the number of weighting vectors is a constant. For this problem, we present a dynamic programming algorithm running in pseudo-polynomial time and a fully polynomial-time approximation scheme (FPTAS).

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research