Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints

DOI10.1016/S0167-5060(08)70323-6zbMath0374.68033OpenAlexW1569458199MaRDI QIDQ4151722

Publication date: 1978

Published in: Algorithmic Aspects of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-5060(08)70323-6

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Algorithms in computer science (68W99)

Related Items

Optimal ordering of statistically dependent tests, A compact labelling scheme for series-parallel graphs, A survey on how the structure of precedence constraints may change the complexity class of scheduling problems, On some complexity properties of N-free posets and posets with bounded decomposition diameter, Can transitive orientation make sandwich problems easier?, Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation, The Parametric Closure Problem, Dynamic expression trees, Exact algorithms for single-machine scheduling with time windows and precedence constraints, On the Complexity of Scheduling to Optimize Average Response Time, N-free posets as generalizations of series-parallel posets, Parallel recognition and decomposition of two terminal series parallel graphs, How to make OR-results available: A proposal for project scheduling, Optimal restricted due date assignment in scheduling, Adamant digraphs, Approximability of single machine scheduling with fixed jobs to minimize total completion time, File space utilization in database conversion, Scheduling UET-UCT series-parallel graphs on two processors, Single-machine scheduling with precedence constraints and position-dependent processing times, Improving local search heuristics for some scheduling problems. I, `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders, A 2-OPT procedure to reduce total inspection time in a serial inspection process, Concurrency and atomicity, A General Framework for Approximating Min Sum Ordering Problems, An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs, Scheduling problems with partially ordered jobs, Confluence up to Garbage, Sequencing with general precedence constraints, Complexity results for scheduling chains on a single machine, Hardness of flow time minimization in a crossdock with a single door and asymmetric handover relations, On Submodular Search and Machine Scheduling, On the measurement of complexity in activity networks, Task scheduling with precedence constraints to minimize the total completion time, Setting due dates to minimize the total weighted possibilistic mean value of the weighted earliness-tardiness costs on a single machine, A structure theory for ordered sets, On the approximability of average completion time scheduling under precedence constraints., Single machine scheduling with a generalized job-dependent cumulative effect, An improved algorithm for parallel machine scheduling under additional resource constraints, Unnamed Item, LAD models, trees, and an analog of the fundamental theorem of arithmetic, On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times., Precedence constrained scheduling to minimize sum of weighted completion times on a single machine, \(N\)-extendible posets, and how to minimize total weighted completion time, Approximating Single Machine Scheduling with Scenarios, Scheduling results applicable to decision-theoretic troubleshooting, A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine, Approximating Weighted Completion Time for Order Scheduling with Setup Times, Lower bounds and algorithms for flowtime minimization on a single machine with set-up times, The permutahedron of series-parallel posets, Job lateness in a two-machine flowshop with setup times separated, A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion, Cross-series-parallel digraphs, Extensions of Decision-Theoretic Troubleshooting: Cost Clusters and Precedence Constraints, Time-critical testing and search problems, Vertex Cover in Graphs with Locally Few Colors, Scheduling to minimize total weighted completion time: Performance guarantees of LP-based heuristics and lower bounds, Scheduling with release dates on a single machine to minimize total weighted completion time, Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint, Precedence theorems and dynamic programming for the single-machine weighted tardiness problem, Single-machine scheduling with supporting tasks, Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints, \(P_ 4\)-trees and substitution decomposition, Scheduling with bully selfish jobs, Bounds on the performance of a heuristic to schedule precedence-related jobs on parallel machines, Single machine scheduling with precedence constraints and positionally dependent processing times, Two scheduling problems in group technology with deteriorating jobs, The complexity of machine scheduling for stability with a single disrupted job, Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness, Single machine scheduling with decreasing linear deterioration under precedence constraints, Single-machine scheduling with an external resource, Improving local search heuristics for some scheduling problems. II, Facets of the generalized permutahedron of a poset, Polyhedral results for position-based scheduling of chains on a single machine, A branch and bound algorithm for the minimum storage-time sequencing problem, Optimal ordering of independent tests with precedence constraints, On strictly optimal schedules for the cumulative cost-optimal scheduling problem, Confluence up to garbage in graph transformation, Single machine precedence constrained scheduling is a Vertex cover problem, Scheduling stochastic jobs with due dates on parallel machines, NP-Complete operations research problems and approximation algorithms, A review of four decades of time-dependent scheduling: main results, new topics, and open problems, Scheduling chain-structured tasks to minimize makespan and mean flow time, A decomposition theory based on a dominance relation and composite jobs, Online Linear Optimization for Job Scheduling Under Precedence Constraints, Integrated optimization of test case selection and sequencing for reliability testing of the mainboard of Internet backbone routers, Base polytopes of series-parallel posets: Linear description and optimization, A Note on Stochastic Scheduling on a Single Machine Subject to Breakdown and Repair, Miscellaneous Digraph Classes, Single-machine scheduling problems with precedence constraints and simple linear deterioration, Polynomial Time Approximation Schemes for the Traveling Repairman and Other Minimum Latency Problems, The poset scheduling problem, Scheduling identical parallel machines to minimize total weighted completion time, Nonpreemptive flowshop scheduling with machine dominance, Decision diagrams for solving a job scheduling problem under precedence constraints, The bandwidth problem for graphs and matrices—a survey, On the complexity of scheduling unit-time jobs with or-precedence constraints, An exact algorithm for the precedence-constrained single-machine scheduling problem