Algorithm for minimizing weighted earliness penalty in single-machine problem

Supachai Pathumnakul, Pius J. Egbelu

Research output: Contribution to journalArticlepeer-review

12 Scopus citations

Abstract

In this paper, the problem of minimizing the weighted earliness penalty in a single-machine scheduling problem is addressed. For this problem, every job is assumed to be available at time zero and must be completed before or on its deadline. No tardy job is allowed. Each job has its own earliness penalty and deadline. The paper identifies several local optimality conditions for sequencing of adjacent jobs. A heuristic algorithm is developed based on these local optimality conditions. Sample problems are solved and the solutions obtained from the heuristic are compared to solutions obtained from the heuristics developed by Chand and Schneeberger. Also, comparisons are performed between the solutions obtained from the heuristic and the optimal solutions obtained from a mathematical modeling approach for problems involving 10 and 15 jobs. The results show that the developed heuristic produces solutions close to optimal in small size problems, and it also outperforms the Chand and Schneeberger's method.

Original languageEnglish (US)
Pages (from-to)780-796
Number of pages17
JournalEuropean Journal of Operational Research
Volume161
Issue number3
DOIs
StatePublished - Feb 16 2005
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Keywords

  • Deadline
  • Earliness
  • Heuristic
  • Scheduling
  • Tardiness

Fingerprint Dive into the research topics of 'Algorithm for minimizing weighted earliness penalty in single-machine problem'. Together they form a unique fingerprint.

Cite this