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 publicationJournal articleAcademic researchpeer-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 languageEnglish
Pages (from-to)3612-3619
Number of pages8
JournalComputers and Operations Research
Volume35
Issue number11
DOIs
Publication statusPublished - 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

Cite this