Free Access

Technical Note—Minimizing Average Flow Time with Parallel Machines

W. A. Horn
W. A. Horn
National Bureau of Standards, Washington, D.C.
Search for more papers by this author

W. A. Horn

National Bureau of Standards, Washington, D.C.

Search for more papers by this author

Published Online:1 Jun 1973https://doi.org/10.1287/opre.21.3.846

Cited by
- Tight (S)ETH-Based Lower Bounds for Pseudopolynomial Algorithms for Bin Packing and Multi-machine Scheduling
  9 June 2026
- An EPTAS for minimizing the total weighted completion time of jobs with release dates on uniformly related machines
  Information and Computation, Vol. 311
- The Power of Proportional Fairness for Nonclairvoyant Polytope Scheduling
  2 March 2026 | SIAM Journal on Computing, Vol. 55, No. 2
- Minimizing total completion time with machine-dependent priority lists
  European Journal of Operational Research, Vol. 315, No. 3
- Developing New Bounds for the Performance Guarantee of the Jump Neighborhood for Scheduling Jobs on Uniformly Related Machines
  19 December 2023 | Mathematics, Vol. 12, No. 1
- Délégation de lots de tâches pour la réduction de la durée moyenne de réalisation
  4 July 2023 | Revue Ouverte d'Intelligence Artificielle, Vol. 4, No. 2
- Scheduling High Multiplicity Jobs on Parallel Multi-Purpose Machines with Setup Times and Machine Available Times
  5 April 2022 | Asia-Pacific Journal of Operational Research, Vol. 39, No. 06
- Performance guarantee of the jump neighborhood for scheduling jobs on uniformly related machines
  14 April 2022 | RAIRO - Operations Research, Vol. 56, No. 2
- Performance guarantees of local search for minsum scheduling problems
  30 September 2020 | Mathematical Programming, Vol. 191, No. 2
- Task Bundle Delegation for Reducing the Flowtime
  19 July 2022
- Exploring Scheduling Algorithms for Parallel Task Graphs: A Modern Game Engine Case Study
  1 August 2022
- Backfilling HPC Jobs with a Multimodal-Aware Predictor
- On the Complexity of Load Balancing in Dynamic Networks
  6 July 2021
- Ideal schedules in parallel machine settings
  European Journal of Operational Research, Vol. 290, No. 2
- Performance analysis and optimality results for data-locality aware tasks scheduling with replicated inputs
  Future Generation Computer Systems, Vol. 111
- An approximation scheme for rejection-allowed single-machine rescheduling
  Computers & Industrial Engineering, Vol. 146
- Green parallel machines scheduling problem: A bi-objective model and a heuristic algorithm to obtain Pareto frontier
  29 May 2019 | Journal of the Operational Research Society, Vol. 71, No. 6
- Greed Works—Online Algorithms for Unrelated Machine Stochastic Scheduling
  Varun Gupta,
  Benjamin Moseley,
  Marc Uetz,
  Qiaomin Xie
  29 January 2020 | Mathematics of Operations Research, Vol. 45, No. 2
- AlloX
  17 April 2020
- Scheduling equal length jobs with eligibility restrictions
  21 February 2019 | Annals of Operations Research, Vol. 285, No. 1-2
- Robust algorithms for total completion time
  Discrete Optimization, Vol. 33
- Scheduling meets n-fold integer programming
  15 November 2017 | Journal of Scheduling, Vol. 21, No. 5
- Discrete convexity in joint winner property
  Discrete Optimization, Vol. 28
- Analysis and Experimental Study of Heuristics for Job Scheduling Reoptimization Problems
  28 June 2017
- On Computing an Optimal Semi-matching
  5 July 2016 | Algorithmica, Vol. 78, No. 3
- Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times
  6 April 2016 | Journal of Scheduling, Vol. 20, No. 2
- Relevant Boolean Programming Problems
  19 October 2016
- Stochastic Online Scheduling on Unrelated Machines
  24 May 2017
- Approximability of average completion time scheduling on unrelated machines
  21 April 2016 | Mathematical Programming, Vol. 161, No. 1-2
- Power of Preemption for Minimizing Total Completion Time on Uniform Parallel Machines
  SIAM Journal on Discrete Mathematics, Vol. 31, No. 1
- Multitasking via alternate and shared processing: Algorithms and complexity
  Discrete Applied Mathematics, Vol. 208
- Approximating Semi-matchings in Streaming and in Two-Party Communication
  25 April 2016 | ACM Transactions on Algorithms, Vol. 12, No. 3
- Minimum Weighted Completion Time
  22 April 2016
- Decentralized utilitarian mechanisms for scheduling games
  Games and Economic Behavior, Vol. 92
- Multipurpose machine scheduling with rejection and identical job processing times
  5 July 2014 | Journal of Scheduling, Vol. 18, No. 1
- Serial batch scheduling on uniform parallel machines to minimize total completion time
  Information Processing Letters, Vol. 114, No. 12
- Reoptimization of the minimum total flow-time scheduling problem
  Sustainable Computing: Informatics and Systems, Vol. 4, No. 4
- Solution algorithms for unrelated machines minmax regret scheduling problem with interval processing times and the total flow time criterion
  8 February 2014 | Annals of Operations Research, Vol. 222, No. 1
- Faster Algorithms for Semi-Matching Problems
  1 May 2014 | ACM Transactions on Algorithms, Vol. 10, No. 3
- A MIP formulation for the minmax regret total completion time in scheduling with unrelated parallel machines
  22 May 2013 | Optimization Letters, Vol. 8, No. 4
- A two-stage Ant Colony optimization algorithm to minimize the makespan on unrelated parallel machines—part II: enhancements and experimentations
  19 June 2012 | Journal of Intelligent Manufacturing, Vol. 25, No. 1
- Scheduling problem with multi-purpose parallel machines
  Discrete Applied Mathematics, Vol. 164
- Minimum Weighted Completion Time
  6 November 2014
- Multiagent Scheduling Fundamentals
  18 December 2013
- Problems, Algorithms and Complexity
  18 December 2013
- Single Machine Problems
  18 December 2013
- Batching Scheduling Problems
  18 December 2013
- Parallel Machine Scheduling Problems
  18 December 2013
- Scheduling Problems with Variable Job Processing Times
  18 December 2013
- Optimal Coordination Mechanisms for Multi-job Scheduling Games
- Approximating Semi-matchings in Streaming and in Two-Party Communication
- Simple matching vs linear assignment in scheduling models with positional effects: A critical review
  European Journal of Operational Research, Vol. 222, No. 3
- Bi-criteria scheduling with machine assignment costs
  International Journal of Production Economics, Vol. 139, No. 1
- Reoptimization of the Minimum Total Flow-Time Scheduling Problem
- Scheduling unrelated parallel machines with resource-assignable sequence-dependent setup times
  6 May 2011 | The International Journal of Advanced Manufacturing Technology, Vol. 57, No. 5-8
- Inner product spaces for MinSum coordination mechanisms
  6 June 2011
- Hybrid tractability of valued constraint problems
  Artificial Intelligence, Vol. 175, No. 9-10
- On Computing an Optimal Semi-matching
- Infinite split scheduling: a new lower bound of total weighted completion time on parallel machines with job release dates and unavailability periods
  7 May 2010 | Annals of Operations Research, Vol. 181, No. 1
- A two-stage Ant Colony Optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times
  20 February 2009 | Journal of Intelligent Manufacturing, Vol. 21, No. 6
- TWO-STAGE FLOWSHOP SCHEDULING PROBLEMS WITH IDENTICAL AND BATCH PROCESSORS
  20 November 2011 | Asia-Pacific Journal of Operational Research, Vol. 27, No. 05
- Neuron network methods of task assignment in multiprocessing system
  12 October 2010 | Optical Memory and Neural Networks, Vol. 19, No. 3
- Scheduling on parallel machines considering job-machine dependency constraints
  Electronic Notes in Discrete Mathematics, Vol. 36
- Bicriteria problems to minimize maximum tardiness and due date assignment cost in various scheduling environments
  Discrete Applied Mathematics, Vol. 158, No. 10
- A priori parallel machines scheduling
  Computers & Industrial Engineering, Vol. 58, No. 3
- Faster Algorithms for Semi-matching Problems (Extended Abstract)
- A New Hybrid Tractable Class of Soft Constraint Problems
- Solving a Multiprocessor Problem by Column Generation and Branch-and-price
  IFAC Proceedings Volumes, Vol. 43, No. 17
- Exact and approximate algorithms for high-multiplicity parallel machine scheduling
  29 July 2009 | Journal of Scheduling, Vol. 12, No. 5
- Generating subproblems in branch and bound algorithms for parallel machines scheduling problem
  Computers & Industrial Engineering, Vol. 57, No. 3
- A note: Simple heuristics for scheduling a maintenance activity on unrelated machines
  Computers & Operations Research, Vol. 36, No. 10
- Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times
  European Journal of Operational Research, Vol. 197, No. 3
- Approximation algorithms for multi-agent scheduling to minimize total weighted completion time
  Information Processing Letters, Vol. 109, No. 16
- Non-identical parallel-machine scheduling research with minimizing total weighted completion times: Models, relaxations and algorithms
  Applied Mathematical Modelling, Vol. 33, No. 4
- Scheduling with processing set restrictions: A survey
  International Journal of Production Economics, Vol. 116, No. 2
- Ant colony optimization algorithm to parallel machine scheduling problem with setups
- Optimal due date assignment in multi-machine scheduling environments
  13 July 2007 | Journal of Scheduling, Vol. 11, No. 3
- A branch-and-bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates
  Computers & Operations Research, Vol. 35, No. 4
- Minimum Weighted Completion Time
- Distribution Stream of Tasks in Dual-Processor System
- Approximability of Average Completion Time Scheduling on Unrelated Machines
- Scheduling on Parallel Processors
- A branch and bound algorithm to minimize total weighted completion time on identical parallel machines with job release dates
- Order Assignment and Scheduling in a Supply Chain
  Zhi-Long Chen,
  Guruprasad Pundoor,
  1 June 2006 | Operations Research, Vol. 54, No. 3
- Semi-matchings for bipartite graphs and load balancing
  Journal of Algorithms, Vol. 59, No. 1
- Scheduling unit length jobs with parallel nested machine processing set restrictions
  Computers & Operations Research, Vol. 33, No. 3
- Sequencing precedence-related jobs on two machines to minimize the weighted completion time
  International Journal of Production Economics, Vol. 100, No. 1
- Heuristics for the Unrelated Parallel Machine Scheduling Problem with Setup Times
  Journal of Intelligent Manufacturing, Vol. 17, No. 1
- A comparison of branch-and-bound algorithms for a family scheduling problem with identical parallel machines
  European Journal of Operational Research, Vol. 167, No. 2
- Multicriteria scheduling
  European Journal of Operational Research, Vol. 167, No. 3
- Complexity of preemptive minsum scheduling on unrelated parallel machines
  Journal of Algorithms, Vol. 57, No. 1
- An enhanced formulation and simple heuristic for scheduling jobs on unrelated parallel machines
  Journal of Information and Optimization Sciences, Vol. 26, No. 1
- Scheduling unrelated parallel machines to minimize total weighted tardiness
  Computers & Operations Research, Vol. 30, No. 12
- Scheduling jobs with piecewise linear decreasing processing times
  4 February 2003 | Naval Research Logistics (NRL), Vol. 50, No. 6
- Semi-matchings for Bipartite Graphs and Load Balancing
- Programação de operações em sistemas com tempo de processamento variável
  Pesquisa Operacional, Vol. 22, No. 3
- Experimental Comparison of Approximation Algorithms for Scheduling Unrelated Parallel Machines
  Tjark Vredeveld,
  Cor Hurkens,
  1 May 2002 | INFORMS Journal on Computing, Vol. 14, No. 2
- Simultaneous Scheduling and Assignment of Processes as a Method of Optimization of Architectural Solutions of Computer Systems
  Automation and Remote Control, Vol. 62, No. 12
- Non-Approximability Results for Scheduling Problems with Minsum Criteria
  Han Hoogeveen,
  Petra Schuurman,
  Gerhard J. Woeginger,
  1 May 2001 | INFORMS Journal on Computing, Vol. 13, No. 2
- Two NP-hardness Results for Preemptive Minsum Scheduling of Unrelated Parallel Machines
  21 June 2001
- Scheduling on Parallel Processors
- A PTAS for the average weighted completion time problem on unrelated machines
  1 January 2000 | Journal of Scheduling, Vol. 3, No. 6
- Lower bounds and algorithms for flowtime minimization on a single machine with set-up times
  Journal of Scheduling, Vol. 3, No. 1
- Polynomial time approximation algorithms for machine scheduling: ten open problems
  Journal of Scheduling, Vol. 2, No. 5
- The Conference Paper‐Reviewer Assignment Problem*
  7 June 2007 | Decision Sciences, Vol. 30, No. 3
- A min-sum 3/2-approximation algorithm for scheduling unrelated parallel machines
  Journal of Scheduling, Vol. 2, No. 2
- Scheduling jobs on unrelated parallel machines to minimize regular total cost functions
  IIE Transactions, Vol. 31, No. 2
- Scheduling on a Constant Number of Machines
- Approximation schemes for minimizing average weighted completion time with release dates
- Minimizing average completion time in the presence of release dates
  Mathematical Programming, Vol. 82, No. 1-2
- A Review of Machine Scheduling: Complexity, Algorithms and Approximability
- Task Scheduling in Networks
  SIAM Journal on Discrete Mathematics, Vol. 10, No. 4
- On the existence of schedules that are near-optimal for both makespan and total weighted completion time
  Operations Research Letters, Vol. 21, No. 3
- Complexity of scheduling problems with multi-purpose machines
  Annals of Operations Research, Vol. 70, No. 0
- Using quadratic programming to solve high multiplicity scheduling problems on parallel machines
  Algorithmica, Vol. 17, No. 2
- Maschinenbelegungsplanung
- Single machine scheduling with batch deliveries
  European Journal of Operational Research, Vol. 94, No. 2
- Scheduling of unrelated parallel machines when machine availability is specified
  27 April 2007 | Production Planning & Control, Vol. 7, No. 4
- Improved scheduling algorithms for minsum criteria
  2 June 2005
- Scheduling on Parallel Processors
- Scheduling jobs that arrive over time
  1 June 2005
- Chapter 1 Applications of network optimization
- Scheduling onM parallel machines subject to random breakdowns to minimize expected mean flow time
  Naval Research Logistics, Vol. 41, No. 5
- Time partitioning based on the job-flow schedule — A new approach to optimum allocation of jobs on machine tools
  The International Journal of Advanced Manufacturing Technology, Vol. 9, No. 3
- Task scheduling in networks
  30 May 2005
- Parallel Processor Scheduling
- An approximation algorithm for the generalized assignment problem
  Mathematical Programming, Vol. 62, No. 1-3
- Parallel Processor Scheduling
- Maschinenbelegungsplanung
- Chapter 9 Sequencing and scheduling: Algorithms and complexity
- Dynamic Optimization of Job Distribution on Machine Tools Using Time Decomposition into Constant Job-Mix Stages
  CIRP Annals, Vol. 41, No. 1
- A state-of-the-art review of parallel-machine scheduling research
  European Journal of Operational Research, Vol. 47, No. 3
- Chapter 2 parallel machines — Efficient algorithms, complexity results
  Annals of Operations Research, Vol. 7, No. 1
- Recent Results in the Theory of Machine Scheduling
- Recent Developments in Deterministic Sequencing and Scheduling: A Survey
- Scheduling jobs to two machines subject to batch arrival ordering
  21 November 2006 | Naval Research Logistics Quarterly, Vol. 26, No. 3
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Flow-Time Sequencing of Independent Tasks on Multiple Processors’ *
  25 May 2016 | INFOR: Information Systems and Operational Research, Vol. 15, No. 3
- Complexity of Machine Scheduling Problems
- Die Komplexität von Scheduling Problemen

Volume 21, Issue 3

May-June 1973

Pages 661-865

Article Information

Metrics

Information

Published Online:June 01, 1973

Cite as

W. A. Horn, (1973) Technical Note—Minimizing Average Flow Time with Parallel Machines. Operations Research 21(3):846-847.

https://doi.org/10.1287/opre.21.3.846

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Technical Note—Minimizing Average Flow Time with Parallel Machines

Volume 21, Issue 3

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News