Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints
From MaRDI portal
Publication:4151722
DOI10.1016/S0167-5060(08)70323-6zbMath0374.68033MaRDI QIDQ4151722
Publication date: 1978
Published in: Algorithmic Aspects of Combinatorics (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68W99: Algorithms in computer science
Related Items
On the Complexity of Scheduling to Optimize Average Response Time, A branch and bound algorithm for the minimum storage-time sequencing problem, Genetic algorithm based scheduling of parallel batch machines with incompatible job families to minimize total weighted tardiness, Task scheduling with precedence constraints to minimize the total completion time, The permutahedron of series-parallel posets, Improving local search heuristics for some scheduling problems. II, Facets of the generalized permutahedron of a poset, `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders, Scheduling problems with partially ordered jobs, Scheduling stochastic jobs with due dates on parallel machines, On the complexity of scheduling unit-time jobs with or-precedence constraints, Single machine scheduling models with deterioration and learning: Handling precedence constraints via priority generation, Approximability of single machine scheduling with fixed jobs to minimize total completion time, A 2-OPT procedure to reduce total inspection time in a serial inspection process, A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion, Scheduling of parallel machines to minimize total completion time subject to s-precedence constraints, Single machine scheduling with decreasing linear deterioration under precedence constraints, Single machine precedence constrained scheduling is a Vertex cover problem, The poset scheduling problem, A compact labelling scheme for series-parallel graphs, On some complexity properties of N-free posets and posets with bounded decomposition diameter, N-free posets as generalizations of series-parallel posets, Parallel recognition and decomposition of two terminal series parallel graphs, Adamant digraphs, File space utilization in database conversion, Concurrency and atomicity, Sequencing with general precedence constraints, Complexity results for scheduling chains on a single machine, On the measurement of complexity in activity networks, A structure theory for ordered sets, Job lateness in a two-machine flowshop with setup times separated, Scheduling with release dates on a single machine to minimize total weighted completion time, \(P_ 4\)-trees and substitution decomposition, On strictly optimal schedules for the cumulative cost-optimal scheduling problem, Base polytopes of series-parallel posets: Linear description and optimization, Scheduling identical parallel machines to minimize total weighted completion time, Dynamic expression trees, Scheduling UET-UCT series-parallel graphs on two processors, On the approximability of average completion time scheduling under precedence constraints., On the single machine serial batching scheduling problem to minimize total completion time with precedence constraints, release dates and identical processing times., Nonpreemptive flowshop scheduling with machine dominance, Scheduling chain-structured tasks to minimize makespan and mean flow time, A decomposition theory based on a dominance relation and composite jobs, How to make OR-results available: A proposal for project scheduling, Improving local search heuristics for some scheduling problems. I, An NC algorithm for finding a minimum weighted completion time schedule on series parallel graphs, 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, A half-integral linear programming relaxation for scheduling precedence-constrained jobs on a single machine, Lower bounds and algorithms for flowtime minimization on a single machine with set-up times, Can transitive orientation make sandwich problems easier?, Single-machine scheduling with deteriorating jobs under a series-parallel graph constraint, Two scheduling problems in group technology with deteriorating jobs, The complexity of machine scheduling for stability with a single disrupted job, Bounds on the performance of a heuristic to schedule precedence-related jobs on parallel machines, A Note on Stochastic Scheduling on a Single Machine Subject to Breakdown and Repair, Approximating Single Machine Scheduling with Scenarios, The bandwidth problem for graphs and matrices—a survey, Unnamed Item, NP-Complete operations research problems and approximation algorithms
