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

EasyChair Preprint no. 2913

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: approximation algorithms, minmax regret, number of late jobs, robust optimization, Scheduling

@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 no. 2913},

  year = {EasyChair, 2020}}