Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs

Chung-Lun Li; T. C.E. Cheng; Z. L. Chen

doi:10.1016/0305-0548(94)E0012-V

Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs

Chung-Lun Li
, T. C.E. Cheng
, Z. L. Chen

Research output: Journal Publications and Reviews › RGC 21 - Publication in refereed journal › peer-review

8 Citations (Scopus)

Abstract

We consider a single-machine scheduling problem in which every job has a given target start time and a due-date. A job is early if processing commences before its start time and is tardy if it is completed after its due-date. The objective is to minimize the weighted number of early and tardy jobs, with the restriction that the start times and due-dates are "agreeable", i.e., the start times must increase in the same sequence as the due-dates. We show that the problem is NP-complete in the strong sense. The complexity issues and algorithms for some special cases of this problem are discussed, and heuristic algorithms are developed for the general problem. Computational experiments are conducted to show the effectiveness of the heuristics. © 1995.

Original language	English
Pages (from-to)	205-219
Journal	Computers and Operations Research
Volume	22
Issue number	2
DOIs	https://doi.org/10.1016/0305-0548(94)E0012-V
Publication status	Published - Feb 1995
Externally published	Yes

Bibliographical note

Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

Access Output

10.1016/0305-0548(94)E0012-V

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

@article{eccbd17320f04975a704f92517f2aef2,

title = "Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs",

abstract = "We consider a single-machine scheduling problem in which every job has a given target start time and a due-date. A job is early if processing commences before its start time and is tardy if it is completed after its due-date. The objective is to minimize the weighted number of early and tardy jobs, with the restriction that the start times and due-dates are {"}agreeable{"}, i.e., the start times must increase in the same sequence as the due-dates. We show that the problem is NP-complete in the strong sense. The complexity issues and algorithms for some special cases of this problem are discussed, and heuristic algorithms are developed for the general problem. Computational experiments are conducted to show the effectiveness of the heuristics. {\textcopyright} 1995.",

author = "Chung-Lun Li and Cheng, \{T. C.E.\} and Chen, \{Z. L.\}",

note = "Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].",

year = "1995",

month = feb,

doi = "10.1016/0305-0548(94)E0012-V",

language = "English",

volume = "22",

pages = "205--219",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd.",

number = "2",

}

TY - JOUR

T1 - Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs

AU - Li, Chung-Lun

AU - Cheng, T. C.E.

AU - Chen, Z. L.

N1 - Publication details (e.g. title, author(s), publication statuses and dates) are captured on an “AS IS” and “AS AVAILABLE” basis at the time of record harvesting from the data source. Suggestions for further amendments or supplementary information can be sent to [email protected].

PY - 1995/2

Y1 - 1995/2

N2 - We consider a single-machine scheduling problem in which every job has a given target start time and a due-date. A job is early if processing commences before its start time and is tardy if it is completed after its due-date. The objective is to minimize the weighted number of early and tardy jobs, with the restriction that the start times and due-dates are "agreeable", i.e., the start times must increase in the same sequence as the due-dates. We show that the problem is NP-complete in the strong sense. The complexity issues and algorithms for some special cases of this problem are discussed, and heuristic algorithms are developed for the general problem. Computational experiments are conducted to show the effectiveness of the heuristics. © 1995.

AB - We consider a single-machine scheduling problem in which every job has a given target start time and a due-date. A job is early if processing commences before its start time and is tardy if it is completed after its due-date. The objective is to minimize the weighted number of early and tardy jobs, with the restriction that the start times and due-dates are "agreeable", i.e., the start times must increase in the same sequence as the due-dates. We show that the problem is NP-complete in the strong sense. The complexity issues and algorithms for some special cases of this problem are discussed, and heuristic algorithms are developed for the general problem. Computational experiments are conducted to show the effectiveness of the heuristics. © 1995.

UR - https://www.scopus.com/pages/publications/0029243319

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-0029243319&origin=recordpage

U2 - 10.1016/0305-0548(94)E0012-V

DO - 10.1016/0305-0548(94)E0012-V

M3 - RGC 21 - Publication in refereed journal

SN - 0305-0548

VL - 22

SP - 205

EP - 219

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 2

ER -

Single-machine scheduling to minimize the weighted number of early and tardy agreeable jobs

Abstract

Bibliographical note

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this