Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity

DOI10.1051/ro:20070012zbMath1377.90024OpenAlexW2128580449MaRDI QIDQ4600609

Marie-Claude Portmann, Mikhail Y. Kovalyov, Mohamed Ali Aloulou

Publication date: 12 January 2018

Published in: RAIRO - Operations Research (Search for Journal in Brave)

Full work available at URL: http://www.numdam.org/item?id=RO_2007__41_1_1_0/

zbMATH Keywords

schedulingsingle machinemaximization problemsschedule flexibilityactive and non-delay schedules

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items (5)

Minimizing total weighted tardiness for scheduling equal-length jobs on a single machine ⋮ Single machine total tardiness maximization problems: complexity and algorithms ⋮ A generic approach to proving NP-hardness of partition type problems ⋮ Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one ⋮ Maximizing total tardiness on a single machine in \(O(n^2)\) time via a reduction to half-product minimization

This page was built for publication: Evaluating flexible solutions in single machine scheduling via objective function maximization: the study of computational complexity