The Single Machine Problem with Quadratic Penalty Function of Completion Times: A Branch-and-Bound Solution

W. Townsend
W. Townsend
Leeds Polytechnic, England
Search for more papers by this author

Leeds Polytechnic, England

Published Online:1 Jan 1978https://doi.org/10.1287/mnsc.24.5.530

Abstract

N jobs are to be sequenced on a single machine, each job carrying a penalty cost which is a quadratic function of its completion time. The objective is to find a sequence which minimizes the total penalty. Criteria are developed for ordering a pair of adjacent jobs in a sequence and these are incorporated into a branch-and-bound procedure.

Cited by
- Optimal designs for order-of-addition screening factorial experiments
  15 July 2025 | Journal of the Korean Statistical Society, Vol. 54, No. 4
- Optimal Designs for Order-of-Addition Two-Level Factorial Experiments
  1 August 2025 | Technometrics, Vol. 67, No. 4
- On-Line Single Machine Scheduling of Unit Time Jobs with Rejection: Minimizing the Maximum Quadratic Completion Time
  20 March 2025 | Asia-Pacific Journal of Operational Research
- Robust Design for Order-of-Addition Experiments
  12 November 2024 | Technometrics, Vol. 67, No. 1
- Combining Lagrangian Relaxation and Neural Network to Solve Single-machine Scheduling Problem
- Scheduling jobs with general truncated learning effects including proportional setup times
  19 April 2022 | Computational and Applied Mathematics, Vol. 41, No. 4
- A statistical perspective on non-deterministic polynomial-time hard ordering problems: Making use of design for order-of-addition experiments
  Computers & Industrial Engineering, Vol. 162
- A mapping-based universal Kriging model for order-of-addition experiments in drug combination studies
  Computational Statistics & Data Analysis, Vol. 157
- Effective Heuristic Algorithms Solving the Jobshop Scheduling Problem with Release Dates
  25 July 2020 | Mathematics, Vol. 8, No. 8
- Online Scheduling with Machine Cost and a Quadratic Objective Function
  17 January 2020
- Study on flow shop scheduling with sum-of-logarithm-processing-times-based learning effects
  30 March 2019 | Journal of Applied Mathematics and Computing, Vol. 61, No. 1-2
- Stochastic single-machine scheduling with random resource arrival times
  28 January 2017 | International Journal of Machine Learning and Cybernetics, Vol. 9, No. 7
- Permutation flow-shop scheduling problem to optimize a quadratic objective function
  8 December 2016 | Engineering Optimization, Vol. 49, No. 9
- Optimally scheduled interventions in the presence of vulnerabilities for modern cyber-physical systems
- The local–global conjecture for scheduling with non-linear cost
  16 January 2016 | Journal of Scheduling, Vol. 20, No. 3
- Pairwise Interchange Argument and Priority Rules
  19 October 2016
- Priority allocation rules for single machine total weighted linear and square tardiness problems
  11 June 2016 | Production Engineering, Vol. 10, No. 4-5
- Machine scheduling problems with a position-dependent deterioration
  Applied Mathematical Modelling, Vol. 39, No. 10-11
- For the airplane refueling problem local precedence implies global precedence
  5 August 2014 | Optimization Letters, Vol. 9, No. 4
- A Note on Scheduling Jobs with Extended Sum-of-Processing-Times-Based and Position-Based Learning Effect
  30 March 2015 | Asia-Pacific Journal of Operational Research, Vol. 32, No. 02
- Some Scheduling Problems on a Single Machine with General Job Effects of Position-Dependent Learning and Start-Time-Dependent Deterioration
  30 March 2015 | Asia-Pacific Journal of Operational Research, Vol. 32, No. 02
- Asymptotic optimality of shortest processing time-based algorithms for flow shop and open shop problems with nonlinear objective functions
  3 January 2014 | Engineering Optimization, Vol. 46, No. 12
- On the asymptotic optimality and improved strategies of SPTB heuristic for open-shop scheduling problem
  11 December 2012 | International Journal of Systems Science, Vol. 45, No. 8
- On the complexity of the single machine scheduling problem minimizing total weighted delay penalty
  Operations Research Letters, Vol. 42, No. 5
- Scheduling deteriorating jobs with chain constraints and a power function of job completion times
  23 April 2014 | Journal of Industrial and Production Engineering, Vol. 31, No. 3
- Single machine scheduling with sum-of-logarithm-processing-times based and position based learning effects
  13 May 2012 | Optimization Letters, Vol. 8, No. 3
- An extended study on an open-shop scheduling problem using the minimisation of the sum of quadratic completion times
  Applied Mathematics and Computation, Vol. 230
- Flowshop scheduling with a general exponential learning effect
  Computers & Operations Research, Vol. 43
- Regular Performance Measures
  23 January 2014
- Dynamic Policies
  23 January 2014
- Application of graph search and genetic algorithms for the single machine scheduling problem with sequence-dependent setup times and quadratic penalty function of completion times
  Computers & Industrial Engineering, Vol. 67
- Scheduling jobs with truncated exponential learning functions
  28 December 2011 | Optimization Letters, Vol. 7, No. 8
- Single machine scheduling with general time-dependent deterioration, position-dependent learning and past-sequence-dependent setup times
  31 July 2012 | Optimization Letters, Vol. 7, No. 8
- Several flow shop scheduling problems with truncated position-based learning effect
  Computers & Operations Research, Vol. 40, No. 12
- Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints
  Operations Research Letters, Vol. 41, No. 5
- Scheduling with a general learning effect
  30 January 2013 | The International Journal of Advanced Manufacturing Technology, Vol. 67, No. 1-4
- Single machine scheduling jobs with a truncated sum-of-processing-times-based learning effect
  17 February 2013 | The International Journal of Advanced Manufacturing Technology, Vol. 67, No. 1-4
- Online scheduling of simple linear deteriorating jobs to minimize the total general completion time
  Theoretical Computer Science, Vol. 487
- Scheduling problems with past-sequence-dependent setup times and general effects of deterioration and learning
  Applied Mathematical Modelling, Vol. 37, No. 7
- Single-machine scheduling problems with an actual time-dependent deterioration
  Applied Mathematical Modelling, Vol. 37, No. 7
- Single machine past-sequence-dependent delivery times scheduling with general position-dependent and time-dependent learning effects
  Applied Mathematical Modelling, Vol. 37, No. 7
- Worst case analysis of flow shop scheduling problems with a time-dependent learning effect
  International Journal of Production Economics, Vol. 142, No. 1
- Single-machine scheduling with effects of exponential learning and general deterioration
  Applied Mathematical Modelling, Vol. 37, No. 4
- Scheduling jobs with a general learning effect model
  Applied Mathematical Modelling, Vol. 37, No. 4
- Several single-machine scheduling problems with general learning effects
  Applied Mathematical Modelling, Vol. 36, No. 11
- A note on minimizing the sum of quadratic completion times on two identical parallel machines
  Information Processing Letters, Vol. 112, No. 19
- A generalisation model of learning and deteriorating effects on a single-machine scheduling with past-sequence-dependent setup times
  International Journal of Computer Integrated Manufacturing, Vol. 25, No. 9
- Minimizing the weighted sum of squared tardiness on a single machine
  Computers & Operations Research, Vol. 39, No. 5
- Single machine scheduling with a general exponential learning effect
  Applied Mathematical Modelling, Vol. 36, No. 2
- Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time-dependent learning effect
  Information Sciences, Vol. 184, No. 1
- On the Performance of Smith’s Rule in Single-Machine Scheduling with Nonlinear Cost
- Worst-case analysis for flow shop scheduling problems with an exponential learning effect
  21 December 2017 | Journal of the Operational Research Society, Vol. 63, No. 1
- Single-machine scheduling with deteriorating jobs
  International Journal of Systems Science, Vol. 43, No. 1
- Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects
  23 June 2011 | Annals of Operations Research, Vol. 191, No. 1
- Scheduling jobs with chain precedence constraints and deteriorating jobs
  21 December 2017 | Journal of the Operational Research Society, Vol. 62, No. 9
- Some single-machine scheduling with both learning and deterioration effects
  Applied Mathematical Modelling, Vol. 35, No. 8
- Single-machine scheduling jobs with exponential learning functions
  Computers & Industrial Engineering, Vol. 60, No. 4
- Single-Machine Scheduling Problems with Decreasing Linear Deterioration and Learning Effects
- Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects
  Applied Mathematical Modelling, Vol. 35, No. 3
- Some single-machine scheduling problems with general effects of learning and deterioration
  Computers & Mathematics with Applications, Vol. 61, No. 1
- Single-machine scheduling with a general sum-of-actual-processing-times-based and job-position-based learning effect
  Applied Mathematical Modelling, Vol. 34, No. 11
- Single machine quadratic penalty function scheduling with deteriorating jobs and group technology
  Applied Mathematical Modelling, Vol. 34, No. 11
- Scheduling jobs with an exponential sum-of-actual-processing-time-based learning effect
  Computers & Mathematics with Applications, Vol. 60, No. 9
- Single machine scheduling with exponential sum-of-logarithm-processing-times based learning effect
  Applied Mathematical Modelling, Vol. 34, No. 10
- Solving a stochastic single machine problem with initial idle time and quadratic objective
  Computers & Operations Research, Vol. 37, No. 7
- Some single-machine scheduling problems with aging effect
- Some single-machine scheduling problems with past-sequence-dependent setup times and a general learning effect
  20 October 2009 | The International Journal of Advanced Manufacturing Technology, Vol. 48, No. 9-12
- Scheduling with past-sequence-dependent setup times and learning effects on a single machine
  19 September 2009 | The International Journal of Advanced Manufacturing Technology, Vol. 48, No. 5-8
- Some scheduling problems with past sequence dependent setup times under the effects of nonlinear deterioration and time-dependent learning
  27 April 2010 | RAIRO - Operations Research, Vol. 44, No. 2
- Greedy by Chance - Stochastic Greedy Algorithms
- A note on single-machine scheduling with decreasing time-dependent job processing times
  Applied Mathematical Modelling, Vol. 34, No. 2
- Single machine scheduling with time-dependent deterioration and exponential learning effect
  Computers & Industrial Engineering, Vol. 58, No. 1
- Deteriorating jobs and learning effects on a single-machine scheduling with past-sequence-dependent setup times
  3 June 2009 | The International Journal of Advanced Manufacturing Technology, Vol. 46, No. 5-8
- Single-machine scheduling with a sum-of-actual-processing-time-based learning effect
  21 December 2017 | Journal of the Operational Research Society, Vol. 61, No. 1
- Scheduling problems with the nonlinear effects of learning and deterioration
  31 March 2009 | The International Journal of Advanced Manufacturing Technology, Vol. 45, No. 7-8
- Single-machine scheduling with both deterioration and learning effects
  18 September 2009 | Annals of Operations Research, Vol. 172, No. 1
- Single-machine scheduling with learning effect and deteriorating jobs
  Computers & Industrial Engineering, Vol. 57, No. 4
- Learning effect and deteriorating jobs in the single machine scheduling problems
  Applied Mathematical Modelling, Vol. 33, No. 10
- A Survey of Data-based Production Scheduling Methods
  Acta Automatica Sinica, Vol. 35, No. 6
- Single machine scheduling problems under the effects of nonlinear deterioration and time-dependent learning
  Mathematical and Computer Modelling, Vol. 50, No. 3-4
- Some Single-machine Scheduling Problems with Actual Time and Position Dependent Learning Effects
  25 January 2019 | Fuzzy Information and Engineering, Vol. 1, No. 2
- Single-machine scheduling with past-sequence-dependent setup times and effects of deterioration and learning
  8 May 2008 | The International Journal of Advanced Manufacturing Technology, Vol. 41, No. 11-12
- A scheduling problem with job values given as a power function of their completion times
  European Journal of Operational Research, Vol. 193, No. 3
- Scheduling jobs on a single machine to maximize the total revenue of jobs
  Computers & Operations Research, Vol. 36, No. 2
- Some Single Machine Scheduling Problems with an Actual Time-Dependent and Position-Dependent Learning Effect
- Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times
  Computers & Mathematics with Applications, Vol. 57, No. 1
- Single-machine scheduling with general learning functions
  Computers & Mathematics with Applications, Vol. 56, No. 8
- Single-machine scheduling with past-sequence-dependent setup times and time-dependent learning effect
  Computers & Industrial Engineering, Vol. 55, No. 3
- Worst-case analysis for flow shop scheduling with a learning effect
  International Journal of Production Economics, Vol. 113, No. 2
- Single-machine scheduling with an actual time-dependent learning effect
  21 December 2017 | Journal of the Operational Research Society, Vol. 58, No. 10
- Single-machine scheduling problems with the effects of learning and deterioration
  Omega, Vol. 35, No. 4
- Single-machine scheduling problems with the time-dependent learning effect
  Computers & Mathematics with Applications, Vol. 53, No. 11
- Single-machine scheduling problems with start-time dependent processing time
  Computers & Mathematics with Applications, Vol. 53, No. 11
- Scheduling on One Processor
- Algorithms with performance guarantees for flow shops with regular objective functions
  IIE Transactions, Vol. 37, No. 12
- Minimizing non-decreasing separable objective functions for the unit-time open shop scheduling problem
  European Journal of Operational Research, Vol. 165, No. 2
- NONCOOPERATIVE GAME ON SCHEDULING: THE SINGLE MACHINE CASE
  IFAC Proceedings Volumes, Vol. 38, No. 1
- Stochastic scheduling subject to machine breakdowns: The preemptive‐repeat model with discounted reward and other criteria
  23 June 2004 | Naval Research Logistics (NRL), Vol. 51, No. 6
- Single machine scheduling with early and quadratic tardy penalties
  Computers & Industrial Engineering, Vol. 46, No. 3
- Average-case analysis of best-first search in two representative directed acyclic graphs
  Artificial Intelligence, Vol. 155, No. 1-2
- Parallel machine scheduling to minimize the sum of quadratic completion times
  IIE Transactions, Vol. 36, No. 1
- Minimizing the sum of squares lateness on a single machine
  European Journal of Operational Research, Vol. 143, No. 1
- Scheduling on One Processor
- Asymmetry in search
  IEEE Transactions on Systems, Man and Cybernetics, Part B (Cybernetics), Vol. 31, No. 5
- An improved precedence rule for single machine sequencing problems with quadratic penalty
  European Journal of Operational Research, Vol. 125, No. 2
- A bicriterion scheduling problem involving total flowtime and total tardiness
  Journal of Information and Optimization Sciences, Vol. 20, No. 2
- Decomposition in single-machine scheduling
  Annals of Operations Research, Vol. 83, No. 0
- A Review of Machine Scheduling: Complexity, Algorithms and Approximability
- General stochastic single-machine scheduling with regular cost functions
  Mathematical and Computer Modelling, Vol. 26, No. 3
- Costs in design of scheduling algorithms: A study on branch-and-bound methodology
  Computers & Industrial Engineering, Vol. 32, No. 1
- Graph search methods for non-order-preserving evaluation functions: applications to job sequencing problems
  Artificial Intelligence, Vol. 86, No. 1
- Optimal sequences in stochastic single machine shops
  Computers & Operations Research, Vol. 23, No. 7
- A scheduling algorithm for tasks described by Time Value Function
  Real-Time Systems, Vol. 10, No. 3
- Solution of the generalized Townsend single machine scheduling model
  European Journal of Operational Research, Vol. 91, No. 1
- Minimizing a weighted quadratic function of job lateness in the single machine system
  International Journal of Production Economics, Vol. 42, No. 3
- Scheduling on One Processor
- Searching graphs with A*: applications to job sequencing
  IEEE Transactions on Systems, Man, and Cybernetics - Part A: Systems and Humans, Vol. 26, No. 1
- Minimizing the weighted sum of quadratic completion times on a single machine
  Naval Research Logistics, Vol. 42, No. 8
- Generalized pairwise interchanges and machine scheduling
  European Journal of Operational Research, Vol. 83, No. 2
- Single machine jobshop scheduling problem with weighted quadratic function of job lateness: A branch-and-bound approach
  Journal of Information and Optimization Sciences, Vol. 16, No. 2
- A Branch-and-Bound approach to solve a Bicriterion Scheduling Problem involving Squared Flowtime and Maximum Tardiness
  Journal of Information and Optimization Sciences, Vol. 15, No. 2
- Single Processor Scheduling
- Minimizing a Quadratic Function of Job Lateness in the Single Machine System
  Journal of Information and Optimization Sciences, Vol. 15, No. 1
- Single Processor Scheduling
- Job sequencing with quadratic penalties: An A*-based graph search approach
- On minimizing the weighted sum of quadratic completion times on a single machine
- A scheduling algorithm for real-time computer systems using time value functions
  IFAC Proceedings Volumes, Vol. 25, No. 26
- A new lower bound approach for single-machine multicriteria scheduling
  Operations Research Letters, Vol. 11, No. 1
- A study on the timeliness property in real-time systems
  Real-Time Systems, Vol. 3, No. 3
- Bicriterion jobshop scheduling with total flowtime and sum of squared lateness
  Engineering Costs and Production Economics, Vol. 21, No. 3
- Algorithms for a class of single-machine weighted tardiness and earliness problems
  European Journal of Operational Research, Vol. 52, No. 2
- Sequencing jobs on a single machine with a common due date and stochastic processing times
  European Journal of Operational Research, Vol. 51, No. 2
- Single machine scheduling with nonlinear cost functions
  Computers & Operations Research, Vol. 18, No. 3
- Parametric precedence relations in single machine scheduling
  Operations Research Letters, Vol. 9, No. 2
- Minimizing a generalized quadratic penalty function of job completion times: An improved branch-and-bound approach
  Engineering Costs and Production Economics, Vol. 18, No. 3
- Component-placement optimization for convectively cooled electronics
  IEEE Transactions on Reliability, Vol. 38, No. 2
- Bicriterion static scheduling research for a single machine
  Omega, Vol. 16, No. 1
- A Single Machine Bicriterion Scheduling Problem and an Optimizing Branch-and-Bound Procedure
  Journal of Information and Optimization Sciences, Vol. 8, No. 3
- Single machine scheduling research
  Omega, Vol. 15, No. 3
- Minimizing a quadratic function of job lateness on a single machine
  Engineering Costs and Production Economics, Vol. 7, No. 3
- A Branch-and-Bound Procedure to Solve a Bicriterion Scheduling Problem
  6 July 2007 | IIE Transactions, Vol. 15, No. 1
- The Sngle Machine Problem with Quadratic Penalty Function
  Journal of Information and Optimization Sciences, Vol. 3, No. 1
- Single Machine Schednling Problem with Quadratic Function of Completion Times-A Modified Approach
  Journal of Information and Optimization Sciences, Vol. 2, No. 2
- A multiple objective decision theoretic approach to one-machine scheduling problems
  Computers & Operations Research, Vol. 7, No. 4

Volume 24, Issue 5

January 1978

Pages 485-586

Article Information

Metrics

Information

Published Online:January 01, 1978

Cite as

W. Townsend, (1978) The Single Machine Problem with Quadratic Penalty Function of Completion Times: A Branch-and-Bound Solution. Management Science 24(5):530-534.

https://doi.org/10.1287/mnsc.24.5.530

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

The Single Machine Problem with Quadratic Penalty Function of Completion Times: A Branch-and-Bound Solution

Abstract

Volume 24, Issue 5

Article Information

Metrics

Information

Cite as

Sign Up for INFORMS Publications Updates and News