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

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

Eugene L. Lawler

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 (97)

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

This page was built for publication: Sequencing Jobs to Minimize Total Weighted Completion Time Subject to Precedence Constraints