Algorithms for some maximization scheduling problems on a single machine

DOI10.1134/S0005117910100061zbMath1203.93126WikidataQ57633870 ScholiaQ57633870MaRDI QIDQ612210

Frank Werner, Alexander A. Lazarev, Evgeny R. Gafarov

Publication date: 3 January 2011

Published in: Automation and Remote Control (Search for Journal in Brave)

zbMATH Keywords

single machinescheduling problemspolynomial algorithmsalternative exact algorithm

Mathematics Subject Classification ID

Applications of optimal control and differential games (49N90) Control/observation systems involving computers (process control, etc.) (93C83) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (3)

Single machine total tardiness maximization problems: complexity and algorithms ⋮ Transforming a pseudo-polynomial algorithm for the single machine total tardiness maximization problem into a polynomial one ⋮ Approximability results for the resource-constrained project scheduling problem with a single type of resources

Cites Work

• Unnamed Item
• Algorithms for special cases of the single machine total tardiness problem and an application to the even-odd partition problem
• A graphical realization of the dynamic programming method for solving NP-hard combinatorial problems
• Dual of the maximum cost minimization problem
• Solution of the single machine total tardiness problem
• A decomposition algorithm for the single machine total tardiness problem
• A special case of the single-machine total tardiness problem is NP-hard
• Minimizing Total Tardiness on One Machine is NP-Hard
• An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs

This page was built for publication: Algorithms for some maximization scheduling problems on a single machine