Download PDFOpen PDF in browser

Complexity Results for Common Due Date Scheduling Problems with Interval Data and Minmax Regret Criterion

EasyChair Preprint 2913

2 pagesDate: March 9, 2020

Abstract

We consider the problem of scheduling independent jobs with a common due date on a single machine with the objective of maximizing the number of early jobs. The processing times are uncertain and take any value from a certain job dependent interval. For measuring the quality of an algorithm for that problem with imprecise data we use the concept of minimizing the maximum regret. We present complexity results and some dominance properties.

Keyphrases: Scheduling, approximation algorithms, minmax regret, number of late jobs, robust optimization

BibTeX entry
BibTeX does not have the right entry for preprints. This is a hack for producing the correct reference:
@booklet{EasyChair:2913,
  author    = {Imed Kacem and Hans Kellerer},
  title     = {Complexity Results for Common Due Date Scheduling Problems with Interval Data and Minmax Regret Criterion},
  howpublished = {EasyChair Preprint 2913},
  year      = {EasyChair, 2020}}
Download PDFOpen PDF in browser