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)


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
Issue number2
Publication statusPublished - 1 Mar 2012


  • LRF heuristic
  • Performance bounds
  • Scheduling

ASJC Scopus subject areas

  • Computer Science(all)
  • Engineering(all)

Cite this