Scheduling partially ordered jobs faster than 2ⁿ

DOI10.1007/978-3-642-23719-5_26MaRDI QIDQ3092238zbMATH OpenOpenAlexFDO

Authors Marek Cygan, Marcin Pilipczuk, Michał Pilipczuk, Jakub Onufry Wojtaszczyk

Publication date 16 September 2011

Published in Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1108.0810

zbMATH Keywords

job schedulingjobs with precedencesmoderately exponential algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Abstract: In the SCHED problem we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. SCHED is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2^n n^O(1) time, and whether there exists an algorithms solving SCHED in O(c^n) time for some constant c < 2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively.

Recommendations

• Scheduling partially ordered jobs faster than \(2^n\)
• scientific article; zbMATH DE number 3894817
• On the approximability of average completion time scheduling under precedence constraints.
• Scheduling problems with partially ordered jobs
• Single Machine Scheduling with Precedence Constraints of Dimension 2

Cited in

(16)

• The poset scheduling problem
• The triangle scheduling problem
• Optimization of schedules with precedence logical conditions
• Moderate exponential-time algorithms for scheduling problems
• Parallel machine scheduling with minimum number of tardy jobs: approximation and exponential algorithms
• Succinct representation of linear extensions via MDDs and its application to scheduling under precedence constraints
• Exponential time algorithms for just-in-time scheduling problems with common due date and symmetric weights
• Precedence scheduling with unit execution time is equivalent to parametrized biclique
• On an extension of the Sort \& Search method with application to scheduling theory
• On exact algorithms for the permutation CSP
• Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
• Decision diagrams for solving a job scheduling problem under precedence constraints
• Scheduling partially ordered jobs faster than \(2^n\)
• Scheduling problems with partially ordered jobs
• Moderate exponential-time algorithms for scheduling problems
• Partially ordered knapsack and applications to scheduling

This page was built for publication: Scheduling partially ordered jobs faster than \(2^{n }\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3092238)