On the complexity of bi-criteria scheduling on a single batch processing machine

L. L. Liu; Chi To Ng; Edwin Tai Chiu Cheng

doi:10.1007/s10951-010-0180-2

On the complexity of bi-criteria scheduling on a single batch processing machine

L. L. Liu, Chi To Ng, Edwin Tai Chiu Cheng

Research output: Journal article publication › Journal article › Academic research › peer-review

12 Citations (Scopus)

Abstract

This paper considers hierarchical bi-criteria scheduling on a single batch processing machine where the primary criterion is the makespan. We show that the problem where the secondary criterion is the total completion time can be solved in polynomial time for a given machine capacity and the problem where the secondary criterion is the (weighted) number of late jobs is (strongly) NP-hard.

Original language	English
Pages (from-to)	629-638
Number of pages	10
Journal	Journal of Scheduling
Volume	13
Issue number	6
DOIs	https://doi.org/10.1007/s10951-010-0180-2
Publication status	Published - 1 Dec 2010

Keywords

Batch processing
Bi-criteria
Complexity
Scheduling

ASJC Scopus subject areas

Software
Artificial Intelligence
General Engineering
Management Science and Operations Research

More information

10.1007/s10951-010-0180-2

Cite this

@article{4d3e554e827542a8867e82b6e6eb02cc,

title = "On the complexity of bi-criteria scheduling on a single batch processing machine",

abstract = "This paper considers hierarchical bi-criteria scheduling on a single batch processing machine where the primary criterion is the makespan. We show that the problem where the secondary criterion is the total completion time can be solved in polynomial time for a given machine capacity and the problem where the secondary criterion is the (weighted) number of late jobs is (strongly) NP-hard.",

keywords = "Batch processing, Bi-criteria, Complexity, Scheduling",

author = "Liu, {L. L.} and Ng, {Chi To} and Cheng, {Edwin Tai Chiu}",

year = "2010",

month = dec,

day = "1",

doi = "10.1007/s10951-010-0180-2",

language = "English",

volume = "13",

pages = "629--638",

journal = "Journal of Scheduling",

issn = "1094-6136",

publisher = "Springer New York",

number = "6",

}

TY - JOUR

T1 - On the complexity of bi-criteria scheduling on a single batch processing machine

AU - Liu, L. L.

AU - Ng, Chi To

AU - Cheng, Edwin Tai Chiu

PY - 2010/12/1

Y1 - 2010/12/1

N2 - This paper considers hierarchical bi-criteria scheduling on a single batch processing machine where the primary criterion is the makespan. We show that the problem where the secondary criterion is the total completion time can be solved in polynomial time for a given machine capacity and the problem where the secondary criterion is the (weighted) number of late jobs is (strongly) NP-hard.

AB - This paper considers hierarchical bi-criteria scheduling on a single batch processing machine where the primary criterion is the makespan. We show that the problem where the secondary criterion is the total completion time can be solved in polynomial time for a given machine capacity and the problem where the secondary criterion is the (weighted) number of late jobs is (strongly) NP-hard.

KW - Batch processing

KW - Bi-criteria

KW - Complexity

KW - Scheduling

UR - http://www.scopus.com/inward/record.url?scp=78649896345&partnerID=8YFLogxK

U2 - 10.1007/s10951-010-0180-2

DO - 10.1007/s10951-010-0180-2

M3 - Journal article

SN - 1094-6136

VL - 13

SP - 629

EP - 638

JO - Journal of Scheduling

JF - Journal of Scheduling

IS - 6

ER -

On the complexity of bi-criteria scheduling on a single batch processing machine

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this