Scheduling start time dependent jobs to minimize the total weighted completion time

A. Bachman, Edwin Tai Chiu Cheng, A. Janiak, Chi To Ng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

60 Citations (Scopus)

Abstract

This paper deals with a single machine scheduling problem with start time dependent job processing times. The job processing times are characterized by decreasing linear functions dependent on their start times. The problem is to find a schedule for which the total weighted completion time is minimized. It is proved that the problem is NP-hard. Some properties of special cases of the general problem are also given. Based on these results, two heuristic algorithms are constructed and their performance is compared.
Original languageEnglish
Pages (from-to)688-693
Number of pages6
JournalJournal of the Operational Research Society
Volume53
Issue number6
DOIs
Publication statusPublished - 1 Jun 2002

Keywords

  • Computational analysis
  • Heuristics
  • Scheduling
  • Single machine
  • Start time dependent processing time

ASJC Scopus subject areas

  • Management of Technology and Innovation
  • Strategy and Management
  • Management Science and Operations Research

Cite this