Convex Resource Allocation Problems on Directed Acyclic Graphs: Duality, Complexity, Special Cases, and Extensions
From MaRDI portal
Publication:5749161
DOI10.1287/moor.15.4.736zbMath0717.90080OpenAlexW2171056894MaRDI QIDQ5749161
Clyde l. Monma, Michael J. Todd, Victor K. Wei, Alexander Schrijver
Publication date: 1990
Published in: Mathematics of Operations Research (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/414c402df23a9d3e4aa25f55906b00c44f70c203
resource allocationdirected acyclic graphprecedence graphLagrangian dualityellipsoid methodseparable convex programmingfully- polynomial approximation scheme
Programming involving graphs or networks (90C35) Convex programming (90C25) Abstract computational complexity for mathematical programming problems (90C60) Resource and cost allocation (including fair division, apportionment, etc.) (91B32)
Related Items
Convex resource allocation for minimizing the makespan in a single machine with job release dates, Single and two-resource allocation algorithms for minimizing the maximal lateness in a single machine, Minimizing the total weighted flow time in a single machine with controllable processing times, Single machine batch scheduling to minimize total completion time and resource consumption costs, Single-machine scheduling with resource-dependent processing times and multiple unavailability periods, A note on resource allocation scheduling with position-dependent workloads, A survey of scheduling with controllable processing times, Complexity and approximation of open shop scheduling to minimize the makespan: a review of models and approaches, Single-machine batch scheduling problem with job rejection and resource dependent processing times, Inverse interval scheduling via reduction on a single machine, Controllable processing times in project and production management: analysing the trade-off between processing times and the amount of resources, Coupled task scheduling with convex resource consumption functions, Single machine scheduling with resource allocation and learning effect considering the rate-modifying activity, Bicriterion scheduling with truncated learning effects and convex controllable processing times, Single-machine past-sequence-dependent setup times scheduling with resource allocation and learning effect, Optimal workforce assignment to operations of a paced assembly line, Scheduling a batching machine with convex resource consumption functions, A branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to meet due dates, A bicriteria approach to minimize the total weighted number of tardy jobs with convex controllable processing times and assignable due dates, Scheduling with due date assignment under special conditions on job processing, Bi-criteria and tri-criteria analysis to minimize maximum lateness makespan and resource consumption for scheduling a single machine, Single machine scheduling with total tardiness criterion and convex controllable processing times, The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times, Minimizing task completion time with the execution set method, Single-machine scheduling with machine unavailability periods and resource dependent processing times, Resource constrained scheduling with general truncated job-dependent learning effect, A bicriteria approach to minimize maximal lateness and resource consumption for scheduling a single machine, Resource cost aware scheduling, Approximation algorithms for the workload partition problem and applications to scheduling with variable processing times, The resource dependent assignment problem with a convex agent cost function, Scheduling malleable tasks with interdependent processing rates: comments and observations, Single-machine scheduling to minimize total convex resource consumption with a constraint on total weighted flow time, A bicriterion approach to time/cost trade-offs in scheduling with convex resource-dependent job processing times and release dates, Just-in-time scheduling with controllable processing times on parallel machines, A tabu-search algorithm for scheduling jobs with controllable processing times on a single machine to meet due-dates, Parallel machine scheduling with a convex resource consumption function, A unified approach for scheduling with convex resource consumption functions using positional penalties, A search method for optimal control of a flow shop system of traditional machines, A unified analysis for the single-machine scheduling problem with controllable and non-controllable variable job processing times, Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling, Allocation of resources in project management, Descent methods for convex essentially smooth minimization
