An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs

DOI10.1007/BF01955675zbMath0858.68041OpenAlexW3173138705MaRDI QIDQ1924401

Xin He, S. Sunder

Publication date: 16 October 1996

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01955675

zbMATH Keywords

NC algorithmminimum weighted completion time scheduling problemtransitive series parallel graphs

Mathematics Subject Classification ID

Distributed algorithms (68W15)

Related Items (1)

Fast parallel heuristics for the job shop scheduling problem

Cites Work

• Parallel recognition and decomposition of two terminal series parallel graphs
• The Two-Processor Scheduling Problem is in Random NC
• Two Processor Scheduling is in $\mathcal{NC}$
• The Recognition of Series Parallel Digraphs
• Decomposition Algorithms for Single-Machine Sequencing with Precedence Relations and Deferral Costs
• Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• A simple parallel tree contraction algorithm
• Optimal Linear Ordering
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs