IDEAS home Printed from https://ideas.repec.org/a/inm/orited/v20y2020i2p93-98.html
   My bibliography  Save this article

Case Article—DeLand Crayon Company: An Application of the Traveling Salesman Problem to Production Scheduling with Sequence-Dependent Setup Times

Author

Listed:
  • B. Madhu Rao

    (School of Business Administration, Stetson University, DeLand, Florida 32723)

  • Petros Xanthopoulos

    (School of Business Administration, Stetson University, DeLand, Florida 32723)

  • Qipeng Phil Zheng

    (School of Business Administration, Stetson University, DeLand, Florida 32723)

Abstract

NP-complete problems such as the traveling salesman problem (TSP) play a prominent role in most advanced undergrad/graduate courses in discrete optimization modeling. Teaching such an important topic from a purely mathematical perspective without discussing specific applications may result in reduced student interest and motivation. The DeLand Crayon Company case introduces students to an application of the TSP to a practical production-planning scenario with realistic data. In crayon production, proper sequencing of colors in production can result in significant savings in total production time. The primary objective of the case is to provide students with hands-on experience in applying the TSP model. The case requires the students to consider variations of the basic model with the goal of encouraging them to think logically through the process of mathematical modeling and to consider the decision-making implications of their models. This case study can be used in undergraduate- and graduate-level courses in linear/integer programming or in production planning. It was implemented as part of a term project in a graduate operations research course with overwhelmingly positive feedback

Suggested Citation

  • B. Madhu Rao & Petros Xanthopoulos & Qipeng Phil Zheng, 2020. "Case Article—DeLand Crayon Company: An Application of the Traveling Salesman Problem to Production Scheduling with Sequence-Dependent Setup Times," INFORMS Transactions on Education, INFORMS, vol. 20(2), pages 93-98, January.
    • Handle: RePEc:inm:orited:v:20:y:2020:i:2:p:93-98
    DOI: 10.1287/ited.2019.0216ca
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ited.2019.0216ca
    Download Restriction: no
    File URL: https://libkey.io/10.1287/ited.2019.0216ca?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Burcu B. Keskin & İbrahim Çapar & Charles R. Sox & Nickolas K. Freeman, 2014. "An Integrated Load-Planning Algorithm for Outbound Logistics at Webb Wheel," Interfaces, INFORMS, vol. 44(5), pages 480-497, October.
    2. Gail W. DePuy, 2009. "Puzzle ---Chain-Reaction: A Puzzle to Demonstrate TSP Formulation," INFORMS Transactions on Education, INFORMS, vol. 10(1), pages 41-44, September.
    3. Steven Moss & Cheryl Dale & Glenn Brame, 2000. "Sequence-Dependent Scheduling at Baxter International," Interfaces, INFORMS, vol. 30(2), pages 70-80, April.
    4. Javier Faulin & Pablo Sarobe & Jorge Simal, 2005. "The DSS LOGDIS Optimizes Delivery Routes for FRILAC’s Frozen Products," Interfaces, INFORMS, vol. 35(3), pages 202-214, June.
    5. Michael A. Trick, 2004. "Using Sports Scheduling to Teach Integer Programming," INFORMS Transactions on Education, INFORMS, vol. 5(1), pages 10-17, September.
    6. James C. Bean & John R. Birge, 1980. "Reducing Travelling Costs and Player Fatigue in the National Basketball Association," Interfaces, INFORMS, vol. 10(3), pages 98-102, June.
    7. Jon Lee & John F. Raffensperger, 2006. "Using AMPL for Teaching the TSP," INFORMS Transactions on Education, INFORMS, vol. 7(1), pages 37-69, September.
    8. Martin J. Chlond, 2016. "Puzzle—TSP at the Movies: Yondu’s Dart Problem," INFORMS Transactions on Education, INFORMS, vol. 16(3), pages 110-111, May.
    9. Surya Sahoo & Seongbae Kim & Byung-In Kim & Bob Kraas & Alexander Popov, 2005. "Routing Optimization for Waste Management," Interfaces, INFORMS, vol. 35(1), pages 24-36, February.
    10. Martin J. Chlond, 2002. "The Traveling Space Telescope Problem," INFORMS Transactions on Education, INFORMS, vol. 3(1), pages 69-71, September.
    11. John J. Bartholdi & Loren K. Platzman & R. Lee Collins & William H. Warden, 1983. "A Minimal Technology Routing System for Meals on Wheels," Interfaces, INFORMS, vol. 13(3), pages 1-8, June.
    12. Chuck Holland & Jack Levis & Ranganath Nuggehalli & Bob Santilli & Jeff Winters, 2017. "UPS Optimizes Delivery Routes," Interfaces, INFORMS, vol. 47(1), pages 8-23, February.
    13. Michael A. Trick & Hakan Yildiz & Tallys Yunes, 2012. "Scheduling Major League Baseball Umpires and the Traveling Umpire Problem," Interfaces, INFORMS, vol. 42(3), pages 232-244, June.
    14. Zhouchun Huang & Qipeng P. Zheng & Eduardo L. Pasiliao & Daniel Simmons, 2017. "Exact algorithms on reliable routing problems under uncertain topology using aggregation techniques for exponentially many scenarios," Annals of Operations Research, Springer, vol. 249(1), pages 141-162, February.
    15. Vangelis F. Magirou, 1986. "The Efficient Drilling of Printed Circuit Boards," Interfaces, INFORMS, vol. 16(4), pages 13-23, August.
    16. Frank Schultmann & Bernd Engels & Otto Rentz, 2003. "Closed-Loop Supply Chains for Spent Batteries," Interfaces, INFORMS, vol. 33(6), pages 57-71, December.
    17. Samuel Gorenstein, 1970. "Printing Press Scheduling for Multi-Edition Periodicals," Management Science, INFORMS, vol. 16(6), pages 373-383, February.
    18. Kent J. Kostuk & Keith A. Willoughby, 2012. "A Decision Support System for Scheduling the Canadian Football League," Interfaces, INFORMS, vol. 42(3), pages 286-295, June.
    19. Massimiliano Caramia & Francesca Guerriero, 2010. "A Milk Collection Problem with Incompatibility Constraints," Interfaces, INFORMS, vol. 40(2), pages 130-143, April.
    20. Robert S. Garfinkel, 1977. "Minimizing Wallpaper Waste, Part 1: A Class of Traveling Salesman Problems," Operations Research, INFORMS, vol. 25(5), pages 741-751, October.
    21. Jeroen Beliën & Jan Colpaert & Liesje De Boeck & Johan Eyckmans & Wouter Leirens, 2013. "Teaching Integer Programming Starting From an Energy Supply Game," INFORMS Transactions on Education, INFORMS, vol. 13(3), pages 129-137, May.
    22. Andreas Alpers & Leslie E. Trotter, 2009. "Teaching Computational Discrete Optimization at the Undergraduate Level," INFORMS Transactions on Education, INFORMS, vol. 9(2), pages 63-69, January.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Dries Goossens & Jeroen Beliën, 2023. "Teaching Integer Programming by Scheduling the Belgian Soccer League," INFORMS Transactions on Education, INFORMS, vol. 23(3), pages 164-172, May.
    2. Guillermo Durán, 2021. "Sports scheduling and other topics in sports analytics: a survey with special reference to Latin America," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 29(1), pages 125-155, April.
    3. Michael J. Fry & Jeffrey W. Ohlmann, 2012. "Introduction to the Special Issue on Analytics in Sports, Part II: Sports Scheduling Applications," Interfaces, INFORMS, vol. 42(3), pages 229-231, June.
    4. Elizabeth L. Bouzarth & Benjamin C. Grannan & John M. Harris & Kevin R. Hutson, 2022. "Scheduling the Valley Baseball League," Interfaces, INFORMS, vol. 52(2), pages 189-197, March.
    5. Iain Dunning & Vishal Gupta & Angela King & Jerry Kung & Miles Lubin & John Silberholz, 2015. "A Course on Advanced Software Tools for Operations Research and Analytics," INFORMS Transactions on Education, INFORMS, vol. 15(2), pages 169-179, January.
    6. Paula Carroll, 2023. "Analytics Modules for Business Students," SN Operations Research Forum, Springer, vol. 4(2), pages 1-20, June.
    7. B. Madhu Rao & Jeroen Beliën, 2014. "Case Article—Production Scheduling at Falcon Die Casting: A Comprehensive Example on the Application of Linear Programming and Its Extensions," INFORMS Transactions on Education, INFORMS, vol. 15(1), pages 150-153, September.
    8. Andrea Manno & Laura Palagi & Simone Sagratella, 2019. "Case Article—Production and Distribution Optimization of Beach Equipment for the Marinero Company," INFORMS Transactions on Education, INFORMS, vol. 19(3), pages 152-154, May.
    9. Konstantinos Paparrizos & Nikolaos Samaras & Angelo Sifaleras, 2015. "Exterior point simplex-type algorithms for linear and network optimization problems," Annals of Operations Research, Springer, vol. 229(1), pages 607-633, June.
    10. Lin, Hung-Yueh & Chen, Guan-Hwa & Lee, Pei-Hao & Lin, Chun-Hsu, 2010. "An interactive optimization system for the location of supplementary recycling depots," Resources, Conservation & Recycling, Elsevier, vol. 54(10), pages 615-622.
    11. Tino Henke & M. Grazia Speranza & Gerhard Wäscher, 2019. "A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes," Annals of Operations Research, Springer, vol. 275(2), pages 321-338, April.
    12. Israel D. Herrera-Granda & Jaime Cadena-Echeverría & Juan C. León-Jácome & Erick P. Herrera-Granda & Danilo Chavez Garcia & Andrés Rosales, 2024. "A Heuristic Procedure for Improving the Routing of Urban Waste Collection Vehicles Using ArcGIS," Sustainability, MDPI, vol. 16(13), pages 1-23, July.
    13. Ostermeier, Manuel & Henke, Tino & Hübner, Alexander & Wäscher, Gerhard, 2021. "Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions," European Journal of Operational Research, Elsevier, vol. 292(3), pages 799-817.
    14. Schweiger, Katharina & Sahamie, Ramin, 2013. "A hybrid Tabu Search approach for the design of a paper recycling network," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 50(C), pages 98-119.
    15. Pearce, Joshua M. & Johnson, Sara J. & Grant, Gabriel B., 2007. "3D-mapping optimization of embodied energy of transportation," Resources, Conservation & Recycling, Elsevier, vol. 51(2), pages 435-453.
    16. Ramiro Saltos & Sebastián Maldonado, 2023. "Case Article—School Timetabling Problem: A Scheduling Problem for High-School Institutions," INFORMS Transactions on Education, INFORMS, vol. 24(1), pages 95-99, September.
    17. Yuan, Shuai & Skinner, Bradley & Huang, Shoudong & Liu, Dikai, 2013. "A new crossover approach for solving the multiple travelling salesmen problem using genetic algorithms," European Journal of Operational Research, Elsevier, vol. 228(1), pages 72-82.
    18. Olcay Polat & Duygu Topaloğlu, 2022. "Collection of different types of milk with multi-tank tankers under uncertainty: a real case study," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 30(1), pages 1-33, April.
    19. Rosanna Cole & Brent Snider, 2020. "Rolling the Dice on Global Supply Chain Sustainability: A Total Cost of Ownership Simulation," INFORMS Transactions on Education, INFORMS, vol. 20(3), pages 165-176, May.
    20. Heßler, Katrin, 2021. "Exact algorithms for the multi-compartment vehicle routing problem with flexible compartment sizes," European Journal of Operational Research, Elsevier, vol. 294(1), pages 188-205.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orited:v:20:y:2020:i:2:p:93-98. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.