Online early work scheduling on parallel machines

Yiwei Jiang, Mengjing Wu, Xin Chen, Jianming Dong, T. C.E. Cheng, Jacek Blazewicz, Min Ji

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

We consider non-preemptive online parallel-machine scheduling with a common due date to maximize the total early work of all the jobs, i.e., the total processing time of the jobs (or parts) completed before the common due date. For the general case of m machines, we provide a parameter lower bound with respect to m. For the online algorithm, we first show that the tight competitive ratio of the classical list scheduling (LS) algorithm is [Formula presented]. We then improve the upper bound on the competitive ratio for the previous algorithm, EFFm, to 1.2956. Additionally, we present a formula to compute the upper bound on the competitive ratio for any given m. For the case of three machines, we improve the lower bound to 1.1878 and propose an improved online algorithm with a tight competitive ratio of 1.2483.

Original languageEnglish
Pages (from-to)855-862
Number of pages8
JournalEuropean Journal of Operational Research
Volume315
Issue number3
DOIs
Publication statusPublished - 16 Jun 2024

Keywords

  • Combinatorial optimization
  • Competitive ratio
  • Early work
  • Online algorithm
  • Parallel-machine scheduling

ASJC Scopus subject areas

  • General Computer Science
  • Modelling and Simulation
  • Management Science and Operations Research
  • Information Systems and Management

Fingerprint

Dive into the research topics of 'Online early work scheduling on parallel machines'. Together they form a unique fingerprint.

Cite this