09-38

Algorithms for Maximizing the Number of Tardy Jobs or Total Tardiness on a Single Machine

by Gafarov, E.R.; Lazarev, A.A.; Werner, F.

 

The paper is published: Automation and Remote Control, Vol. 71, No. 10, 2010, 2070 - 2084 (under the title: Algorithms for Some Maximization Problems on a Single Machine; Russian version in Avtomatika i Telemekhanika, No. 10, 2010, 63 - 79).

 

Preprint series: 09-38, Preprints

MSC:
90B35 Scheduling theory, See also {68M20}

 

Abstract: In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total tardiness $1||\max \sum T_j$ and for the problem of maximizing the number of tardy jobs $1||\max \sum U_j$. In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between the jobs. We show that problem $1||\max \sum U_j$ is polynomially solvable. For several special cases of problem $1||\max \sum T_j$, we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the latter problem and an alternative exact algorithm.

Keywords: Scheduling; Single machine problems; Maximization problems; Total tardiness; Number of Tardy Jobs


The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.

Letzte Änderung: 01.03.2018 - Ansprechpartner:

Sie können eine Nachricht versenden an: Webmaster
Sicherheitsabfrage:
Captcha
 
Lösung: