An efficient algorithm for minimizing earliness, tardiness, and due-date costs for equal-sized jobs

Chung Lun Li; Gur Mosheiov; Uri Yovel

doi:10.1016/j.cor.2007.03.006

An efficient algorithm for minimizing earliness, tardiness, and due-date costs for equal-sized jobs

Chung Lun Li, Gur Mosheiov, Uri Yovel

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

6 Citations (Scopus)

Abstract

We consider a single-machine scheduling problem with equal-sized jobs. The objective is to minimize the maximum weighted earliness-tardiness and due-date costs. We present an algorithm to solve this problem. Our algorithm makes use of bottleneck jobs and priority queues, and has a computational complexity of O (n4log n). This complexity is a significant improvement of the existing algorithm in the literature.

Original language	English
Pages (from-to)	3612-3619
Number of pages	8
Journal	Computers and Operations Research
Volume	35
Issue number	11
DOIs	https://doi.org/10.1016/j.cor.2007.03.006
Publication status	Published - 1 Nov 2008

Keywords

Analysis of algorithms
Due-date assignment
Earliness-tardiness
Scheduling

ASJC Scopus subject areas

Information Systems and Management
Management Science and Operations Research
Applied Mathematics
Modelling and Simulation
Transportation

More information

10.1016/j.cor.2007.03.006

http://hdl.handle.net/10397/1842

Cite this

@article{ec3d716eb4cc45d78ce6a7fc994a384f,

title = "An efficient algorithm for minimizing earliness, tardiness, and due-date costs for equal-sized jobs",

abstract = "We consider a single-machine scheduling problem with equal-sized jobs. The objective is to minimize the maximum weighted earliness-tardiness and due-date costs. We present an algorithm to solve this problem. Our algorithm makes use of bottleneck jobs and priority queues, and has a computational complexity of O (n4log n). This complexity is a significant improvement of the existing algorithm in the literature.",

keywords = "Analysis of algorithms, Due-date assignment, Earliness-tardiness, Scheduling",

author = "Li, \{Chung Lun\} and Gur Mosheiov and Uri Yovel",

year = "2008",

month = nov,

day = "1",

doi = "10.1016/j.cor.2007.03.006",

language = "English",

volume = "35",

pages = "3612--3619",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

number = "11",

}

TY - JOUR

T1 - An efficient algorithm for minimizing earliness, tardiness, and due-date costs for equal-sized jobs

AU - Li, Chung Lun

AU - Mosheiov, Gur

AU - Yovel, Uri

PY - 2008/11/1

Y1 - 2008/11/1

N2 - We consider a single-machine scheduling problem with equal-sized jobs. The objective is to minimize the maximum weighted earliness-tardiness and due-date costs. We present an algorithm to solve this problem. Our algorithm makes use of bottleneck jobs and priority queues, and has a computational complexity of O (n4log n). This complexity is a significant improvement of the existing algorithm in the literature.

AB - We consider a single-machine scheduling problem with equal-sized jobs. The objective is to minimize the maximum weighted earliness-tardiness and due-date costs. We present an algorithm to solve this problem. Our algorithm makes use of bottleneck jobs and priority queues, and has a computational complexity of O (n4log n). This complexity is a significant improvement of the existing algorithm in the literature.

KW - Analysis of algorithms

KW - Due-date assignment

KW - Earliness-tardiness

KW - Scheduling

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

U2 - 10.1016/j.cor.2007.03.006

DO - 10.1016/j.cor.2007.03.006

M3 - Journal article

SN - 0305-0548

VL - 35

SP - 3612

EP - 3619

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 11

ER -

An efficient algorithm for minimizing earliness, tardiness, and due-date costs for equal-sized jobs

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this