Single-machine scheduling with trade-off between number of tardy jobs and resource allocation

Edwin Tai Chiu Cheng; Z. L. Chen; Chung Lun Li

doi:10.1016/S0167-6377(96)00035-1

Single-machine scheduling with trade-off between number of tardy jobs and resource allocation

Edwin Tai Chiu Cheng, Z. L. Chen, Chung Lun Li

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

31 Citations (Scopus)

Abstract

We consider a single-machine scheduling problem in which job processing times are controllable through the allocation of a limited resource. The amount of resource consumption of a job is assumed to be linearly related to the job processing time. The performance criteria are the total resource consumption and the number of tardy jobs. Our objective is to construct the trade-off curve between the total amount of resource consumed and the number of tardy jobs. An NP-hardness proof is presented for the problem of minimizing the total amount of allocated resource subject to a limited number of tardy jobs. A pseudo-polynomial-time dynamic programming algorithm is proposed for constructing the trade-off curve. This dynamic program can be generalized to the case where the job processing time is a decreasing function of the amount of allocated resource.

Original language	English
Pages (from-to)	237-242
Number of pages	6
Journal	Operations Research Letters
Volume	19
Issue number	5
DOIs	https://doi.org/10.1016/S0167-6377(96)00035-1
Publication status	Published - 1 Nov 1996

Keywords

Resource allocation
Scheduling
Sequencing
Time-cost trade-offs

ASJC Scopus subject areas

Management Science and Operations Research
Statistics, Probability and Uncertainty
Discrete Mathematics and Combinatorics
Modelling and Simulation

More information

10.1016/S0167-6377(96)00035-1

Cite this

@article{84290e4f607840fb83ed23a53c8e6295,

title = "Single-machine scheduling with trade-off between number of tardy jobs and resource allocation",

abstract = "We consider a single-machine scheduling problem in which job processing times are controllable through the allocation of a limited resource. The amount of resource consumption of a job is assumed to be linearly related to the job processing time. The performance criteria are the total resource consumption and the number of tardy jobs. Our objective is to construct the trade-off curve between the total amount of resource consumed and the number of tardy jobs. An NP-hardness proof is presented for the problem of minimizing the total amount of allocated resource subject to a limited number of tardy jobs. A pseudo-polynomial-time dynamic programming algorithm is proposed for constructing the trade-off curve. This dynamic program can be generalized to the case where the job processing time is a decreasing function of the amount of allocated resource.",

keywords = "Resource allocation, Scheduling, Sequencing, Time-cost trade-offs",

author = "Cheng, {Edwin Tai Chiu} and Chen, {Z. L.} and Li, {Chung Lun}",

year = "1996",

month = nov,

day = "1",

doi = "10.1016/S0167-6377(96)00035-1",

language = "English",

volume = "19",

pages = "237--242",

journal = "Operations Research Letters",

issn = "0167-6377",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - Single-machine scheduling with trade-off between number of tardy jobs and resource allocation

AU - Cheng, Edwin Tai Chiu

AU - Chen, Z. L.

AU - Li, Chung Lun

PY - 1996/11/1

Y1 - 1996/11/1

N2 - We consider a single-machine scheduling problem in which job processing times are controllable through the allocation of a limited resource. The amount of resource consumption of a job is assumed to be linearly related to the job processing time. The performance criteria are the total resource consumption and the number of tardy jobs. Our objective is to construct the trade-off curve between the total amount of resource consumed and the number of tardy jobs. An NP-hardness proof is presented for the problem of minimizing the total amount of allocated resource subject to a limited number of tardy jobs. A pseudo-polynomial-time dynamic programming algorithm is proposed for constructing the trade-off curve. This dynamic program can be generalized to the case where the job processing time is a decreasing function of the amount of allocated resource.

AB - We consider a single-machine scheduling problem in which job processing times are controllable through the allocation of a limited resource. The amount of resource consumption of a job is assumed to be linearly related to the job processing time. The performance criteria are the total resource consumption and the number of tardy jobs. Our objective is to construct the trade-off curve between the total amount of resource consumed and the number of tardy jobs. An NP-hardness proof is presented for the problem of minimizing the total amount of allocated resource subject to a limited number of tardy jobs. A pseudo-polynomial-time dynamic programming algorithm is proposed for constructing the trade-off curve. This dynamic program can be generalized to the case where the job processing time is a decreasing function of the amount of allocated resource.

KW - Resource allocation

KW - Scheduling

KW - Sequencing

KW - Time-cost trade-offs

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

U2 - 10.1016/S0167-6377(96)00035-1

DO - 10.1016/S0167-6377(96)00035-1

M3 - Journal article

SN - 0167-6377

VL - 19

SP - 237

EP - 242

JO - Operations Research Letters

JF - Operations Research Letters

IS - 5

ER -

Single-machine scheduling with trade-off between number of tardy jobs and resource allocation

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this