Performance bound analysis of a heuristic for the total weighted flowtime problem with fixed delivery dates

Research output: Journal article publicationJournal articleAcademic researchpeer-review

1 Citation (Scopus)

Abstract

We consider single-machine scheduling with fixed delivery dates, which are given or determined before the jobs are processed. A job is delivered on the earliest fixed delivery date that is no earlier than its completion time. The flowtime of a job is defined as its delivery date. The objective is to minimize the total weighted flowtime of the jobs. The largest ratio first (LRF) rule is a heuristic that sequences jobs in nonincreasing order of wj/pj, where pjand wjare the processing time and weight of job Jj, respectively. We investigate the performance bounds of the LRF heuristic under different scenarios of the problem. We conducted computational experiments to test the performance of the heuristic. The results show that the LRF heuristic is able to produce near-optimal and optimal solutions.
Original languageEnglish
Pages (from-to)451-456
Number of pages6
JournalComputers and Industrial Engineering
Volume62
Issue number2
DOIs
Publication statusPublished - 1 Mar 2012

Keywords

  • LRF heuristic
  • Performance bounds
  • Scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this