The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective

Research output: Contribution to journalArticlepeer-review

29 Scopus citations

Abstract

Single machine scheduling is a classical optimization problem that depicts multiple real life systems in which a single resource (the machine) represents the whole system or the bottleneck operation of the system. In this paper we consider the problem under a weighted completion time performance metric in which the processing time of the tasks to perform (the jobs) are uncertain, but can only take values from closed intervals. The objective is then to find a solution that minimizes the maximum absolute regret for any possible realization of the processing times. We present an exact branch-and-bound method to solve the problem, and conduct a computational experiment to ascertain the possibilities and limitations of the proposed method. The results show that the algorithm is able to optimally solve instances of moderate size (25-40 jobs depending on the characteristics of the instance).

Original languageEnglish
Pages (from-to)141-152
Number of pages12
JournalComputers and Operations Research
Volume66
DOIs
StatePublished - 1 Feb 2016
Externally publishedYes

Keywords

  • Branch-and-bound
  • Robust optimization
  • Scheduling
  • Single machine
  • Uncertainty

Fingerprint

Dive into the research topics of 'The robust (minmax regret) single machine scheduling with interval processing times and total weighted completion time objective'. Together they form a unique fingerprint.

Cite this