article

Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic Assignment/LP Approach

Authors:

A. M. Geoffrion,

G. W. GravesAuthors Info & Claims

Operations Research, Volume 24, Issue 4

Pages 595 - 610

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

Published: 01 August 1976 Publication History

Abstract

Production orders for a number of products must be scheduled on a number of similar production lines so as to minimize the sum of product-dependent changeover costs, production costs, and time-constraint penalties. We treat the problem by a quadratic assignment algorithm with a linear programming adjustment, and describe a successful practical application for chemical reactor scheduling.

References

[1]

E. BALAS, L. T. ENOS, AND G. W. GRAVES, "Computerized Scheduling of Printing Operations," presented at the Spring Conference of the Graphic Com-munications Computer Association, May 23-25,1973, Toronto.

Google Scholar

[2]

J. E. DAY AND M. P. HOTTENSTEIN, "Review of Sequencing Research," Naval Res. Log. Quart. 17,11-39 ( 1970).

Crossref

Google Scholar

[3]

R. H. DEANE AND E. R. WHITE, "Balancing Workloads and Minimizing Setup Costs in the Parallel Processing Shop," Opnl. Res. Quart. 26, 45-53 (1975).

Crossref

Google Scholar

[4]

S. E. ELMAGHRABY AND A. N. ELSHAFEI, "The Scheduling of Jobs on Parailel Processors: A Survey and Annotated Bibliography," OR Report No. 97, Program in Operations Research, North Carolina State University at Raleigh, September 1974.

Google Scholar

[5]

A. M. GEOFFRION AND R. E. MAUSTEN, "Integer Programming Algorithms: A Framework and State-of-the-Art Survey," Management Sci. 18, 465-491 (May 1972).

Crossref

Google Scholar

[6]

G. W. GRAVES AND A. B. WHINSTON, "An Algorithm for the Quadratic Assignment Problem," Management Sci. 17, 453-471 (1970).

Digital Library

Google Scholar

[7]

T. PRABHAKAR, "Some Scheduling Applications in the Chemical Industry," in Symposium on the Theory of Scheduling and Its Applications, No. 86, Springer-Verlag, 1973.

Google Scholar

[8]

T. PRABHAKAR, "A Production Scheduling Problem with Sequencing Considerations," Management Sci. 21,34-42 (1974).

Digital Library

Google Scholar

[9]

M. RADKE, "Sensitivity Analysis in Discrete Optimization," Ph.D. Thesis, Graduate School of Management, UCLA, September 1975 (available as Working Paper No. 240, Western Management Science Institute, UCLA).

Google Scholar

[10]

A. C. WILLIAMS, "Some Modeling Principles for M.I.P.'s," presented at the VIII International Symposium on Mathematical Programming, Stanford University, August 1973.

Google Scholar

Cited By

View all

Benavides XCeberio JHernando LLozano JSilva SPaquete L(2023)New Knowledge about the Elementary Landscape Decomposition for Solving the Quadratic Assignment ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590369(239-247)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590369
Waddell LPhillips JLiu TDhar S(2023)An LP-based characterization of solvable QAP instances with chess-board and graded structuresJournal of Combinatorial Optimization10.1007/s10878-023-01044-345:5Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1007/s10878-023-01044-3
Graham NHu HIm JLi XWolkowicz H(2022)A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAPINFORMS Journal on Computing10.1287/ijoc.2022.116134:4(2125-2143)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1287/ijoc.2022.1161
Show More Cited By

Scheduling Parallel Production Lines with Changeover Costs: Practical Application of a Quadratic Assignment/LP Approach
1. Applied computing
2. Theory of computation
  1. Design and analysis of algorithms
    1. Approximation algorithms analysis
    2. Online algorithms
      1. Online learning algorithms
  2. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Some Optimum Algorithms for Scheduling Problems with Changeover Costs

We consider a production line that can produce one of n items per day. The demand schedule for all items is known in advance, and all items must be produced on or before their deadlines. We want a production schedule that meets all demand deadlines and ...
A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs

Changeover costs and times are central to numerous manufacturing operations. These costs arise whenever work centers capable of processing only one product at a time switch from the manufacture of one product to another. Although many researchers have ...
Facets and Reformulations for Solving Production Planning With Changeover Costs

We study a scheduling problem with changeover costs and capacity constraints. The problem is NP-complete, and combinatorial algorithms for solving it have not performed well. We identify a general class of facets that subsumes as special cases some ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Operations Research Volume 24, Issue 4

August 1976

203 pages

ISSN:0030-364X

Issue’s Table of Contents

Publisher

INFORMS

Linthicum, MD, United States

Publication History

Published: 01 August 1976

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

24
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Benavides XCeberio JHernando LLozano JSilva SPaquete L(2023)New Knowledge about the Elementary Landscape Decomposition for Solving the Quadratic Assignment ProblemProceedings of the Genetic and Evolutionary Computation Conference10.1145/3583131.3590369(239-247)Online publication date: 15-Jul-2023
https://dl.acm.org/doi/10.1145/3583131.3590369
Waddell LPhillips JLiu TDhar S(2023)An LP-based characterization of solvable QAP instances with chess-board and graded structuresJournal of Combinatorial Optimization10.1007/s10878-023-01044-345:5Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1007/s10878-023-01044-3
Graham NHu HIm JLi XWolkowicz H(2022)A Restricted Dual Peaceman-Rachford Splitting Method for a Strengthened DNN Relaxation for QAPINFORMS Journal on Computing10.1287/ijoc.2022.116134:4(2125-2143)Online publication date: 1-Jul-2022
https://dl.acm.org/doi/10.1287/ijoc.2022.1161
Abdel-Baset MWu HZhou YAbdel-Fatah L(2017)Elite opposition-flower pollination algorithm for quadratic assignment problemJournal of Intelligent & Fuzzy Systems: Applications in Engineering and Technology10.3233/JIFS-16214133:2(901-911)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.3233/JIFS-162141
Acan AÜnveren A(2015)A great deluge and tabu search hybrid with two-stage memory support for quadratic assignment problemApplied Soft Computing10.1016/j.asoc.2015.06.06136:C(185-203)Online publication date: 1-Nov-2015
https://dl.acm.org/doi/10.1016/j.asoc.2015.06.061
Bragin MLuh PYan JYu NStern G(2015)Convergence of the Surrogate Lagrangian Relaxation MethodJournal of Optimization Theory and Applications10.1007/s10957-014-0561-3164:1(173-201)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1007/s10957-014-0561-3
Makarychev KManokaran RSviridenko M(2014)Maximum Quadratic Assignment ProblemACM Transactions on Algorithms10.1145/262967210:4(1-18)Online publication date: 13-Aug-2014
https://dl.acm.org/doi/10.1145/2629672
Chaparala ANovoa CQasem ALathrop SAlameda J(2014)A SIMD Solution for the Quadratic Assignment Problem with GPU AccelerationProceedings of the 2014 Annual Conference on Extreme Science and Engineering Discovery Environment10.1145/2616498.2616521(1-8)Online publication date: 13-Jul-2014
https://dl.acm.org/doi/10.1145/2616498.2616521
Rostami BMalucelli F(2014)A revised reformulation-linearization technique for the quadratic assignment problemDiscrete Optimization10.1016/j.disopt.2014.08.00314:C(97-103)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.disopt.2014.08.003
Adams WWaddell L(2014)Linear programming insights into solvable cases of the quadratic assignment problemDiscrete Optimization10.1016/j.disopt.2014.07.00114:C(46-60)Online publication date: 1-Nov-2014
https://dl.acm.org/doi/10.1016/j.disopt.2014.07.001
Show More Cited By

Abstract

References

Cited By

Recommendations

Some Optimum Algorithms for Scheduling Problems with Changeover Costs

A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs

Facets and Reformulations for Solving Production Planning With Changeover Costs

Comments

Information

Published In

Publisher

Publication History

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations