IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v46y1998i6p872-882.html
   My bibliography  Save this article

Probabilistic Analysis and Practical Algorithms for the Flow Shop Weighted Completion Time Problem

Author

Listed:
  • Philip Kaminsky

    (University of California, Berkeley, California)

  • David Simchi-Levi

    (Northwestern University, Chicago, Illinois)

Abstract

In the flow shop weighted completion time problem, a set of jobs has to be processed on m machines. Every machine has to process each one of the jobs, and every job has the same routing through the machines. The objective is to determine a sequence of the jobs on the machines so as to minimize the sum of the weighted completion times of all jobs on the final machine. In this paper, we present a characterization of the asymptotic optimal solution value for general distributions of the job processing times and weights. In particular, we show that the optimal objective value of this problem is asymptotically equivalent to certain single and parallel machine scheduling problems. This characterization leads to a better understanding of the effectiveness of the celebrated weighted shortest processing time algorithm, as well as to the development of an effective algorithm closely related to the profile fitting heuristic, which was previously utilized for flow shop makespan problems. Computational results show the effectiveness of WSPT and this modified profile fitting heuristic on a set of random test problems.

Suggested Citation

  • Philip Kaminsky & David Simchi-Levi, 1998. "Probabilistic Analysis and Practical Algorithms for the Flow Shop Weighted Completion Time Problem," Operations Research, INFORMS, vol. 46(6), pages 872-882, December.
    • Handle: RePEc:inm:oropre:v:46:y:1998:i:6:p:872-882
    DOI: 10.1287/opre.46.6.872
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.46.6.872
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.46.6.872?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. Julien Bramel & David Simchi-Levi, 1995. "A Location Based Heuristic for General Routing Problems," Operations Research, INFORMS, vol. 43(4), pages 649-660, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Hui Liu & Maurice Queyranne & David Simchi‐Levi, 2005. "On the asymptotic optimality of algorithms for the flow shop problem with release dates," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(3), pages 232-242, April.
    2. Ali Diabat & Claudia Archetti & Waleed Najy, 2021. "The Fixed-Partition Policy Inventory Routing Problem," Transportation Science, INFORMS, vol. 55(2), pages 353-370, March.
    3. Anton J. Kleywegt & Vijay S. Nori & Martin W. P. Savelsbergh, 2004. "Dynamic Programming Approximations for a Stochastic Inventory Routing Problem," Transportation Science, INFORMS, vol. 38(1), pages 42-70, February.
    4. Anton J. Kleywegt & Vijay S. Nori & Martin W. P. Savelsbergh, 2002. "The Stochastic Inventory Routing Problem with Direct Deliveries," Transportation Science, INFORMS, vol. 36(1), pages 94-118, February.
    5. Vishal Gaur & Marshall L. Fisher, 2004. "A Periodic Inventory Routing Problem at a Supermarket Chain," Operations Research, INFORMS, vol. 52(6), pages 813-822, December.
    6. Peter Francis & Karen Smilowitz & Michal Tzur, 2006. "The Period Vehicle Routing Problem with Service Choice," Transportation Science, INFORMS, vol. 40(4), pages 439-454, November.
    7. J. G. Dai & Gideon Weiss, 2002. "A Fluid Heuristic for Minimizing Makespan in Job Shops," Operations Research, INFORMS, vol. 50(4), pages 692-707, August.
    8. Oğuz Solyalı & Jean-François Cordeau & Gilbert Laporte, 2012. "Robust Inventory Routing Under Demand Uncertainty," Transportation Science, INFORMS, vol. 46(3), pages 327-340, August.
    9. Patrick Jaillet & Jonathan F. Bard & Liu Huang & Moshe Dror, 2002. "Delivery Cost Approximations for Inventory Routing Problems in a Rolling Horizon Framework," Transportation Science, INFORMS, vol. 36(3), pages 292-300, August.
    10. Diabat, Ali & Bianchessi, Nicola & Archetti, Claudia, 2024. "On the zero-inventory-ordering policy in the inventory routing problem," European Journal of Operational Research, Elsevier, vol. 312(3), pages 1024-1038.
    11. Ziye Tang & Yang Jiao & R. Ravi, 2022. "Combinatorial Heuristics for Inventory Routing Problems," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 370-384, January.
    12. Zhi-Long Chen & Nicholas G. Hall, 2007. "Supply Chain Scheduling: Conflict and Cooperation in Assembly Systems," Operations Research, INFORMS, vol. 55(6), pages 1072-1089, December.
    13. Philip Kaminsky & David Simchi-Levi, 2001. "The Asymptotic Optimality of the SPT Rule for the Flow Shop Mean Completion Time Problem," Operations Research, INFORMS, vol. 49(2), pages 293-304, April.
    14. Oğuz Solyalı & Haldun Süral, 2011. "A Branch-and-Cut Algorithm Using a Strong Formulation and an A Priori Tour-Based Heuristic for an Inventory-Routing Problem," Transportation Science, INFORMS, vol. 45(3), pages 335-345, August.
    15. Ali Ekici & Okan Örsan Özener & Gültekin Kuyzu, 2015. "Cyclic Delivery Schedules for an Inventory Routing Problem," Transportation Science, INFORMS, vol. 49(4), pages 817-829, November.
    16. Jin-Hwa Song & Martin Savelsbergh, 2007. "Performance Measurement for Inventory Routing," Transportation Science, INFORMS, vol. 41(1), pages 44-54, February.
    17. Mabel C. Chou & Hui Liu & Maurice Queyranne & David Simchi-Levi, 2006. "On the Asymptotic Optimality of a Simple On-Line Algorithm for the Stochastic Single-Machine Weighted Completion Time Problem and Its Extensions," Operations Research, INFORMS, vol. 54(3), pages 464-474, June.
    18. Jaeheon Jung & Kamlesh Mathur, 2007. "An Efficient Heuristic Algorithm for a Two-Echelon Joint Inventory and Routing Problem," Transportation Science, INFORMS, vol. 41(1), pages 55-73, February.
    19. Luca Bertazzi & Lap Mui Ann Chan, 2014. "Analysis of the Best Double Frequency Policy in the Single Link Problem with Discrete Shipping Times," Journal of Optimization Theory and Applications, Springer, vol. 163(1), pages 286-309, October.
    20. Philip Kaminsky & Onur Kaya, 2008. "Scheduling and due‐date quotation in a make‐to‐order supply chain," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(5), pages 444-458, August.
    21. Kaminsky, Philip & Kaya, Onur, 2008. "Inventory positioning, scheduling and lead-time quotation in supply chains," International Journal of Production Economics, Elsevier, vol. 114(1), pages 276-293, July.
    22. Philip Kaminsky, 2003. "The effectiveness of the longest delivery time rule for the flow shop delivery time problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 50(3), pages 257-272, April.
    23. Sonntag, Danja R. & Schrotenboer, Albert H. & Kiesmüller, Gudrun P., 2023. "Stochastic inventory routing with time-based shipment consolidation," European Journal of Operational Research, Elsevier, vol. 306(3), pages 1186-1201.

    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. Craig A. Tovey, 2002. "Tutorial on Computational Complexity," Interfaces, INFORMS, vol. 32(3), pages 30-61, June.
    2. Park, Hyeongjun & Park, Dongjoo & Jeong, In-Jae, 2016. "An effects analysis of logistics collaboration in last-mile networks for CEP delivery services," Transport Policy, Elsevier, vol. 50(C), pages 115-125.
    3. César Rego, 1998. "A Subpath Ejection Method for the Vehicle Routing Problem," Management Science, INFORMS, vol. 44(10), pages 1447-1459, October.
    4. Mahmoudi, Monirehalsadat & Zhou, Xuesong, 2016. "Finding optimal solutions for vehicle routing problem with pickup and delivery services with time windows: A dynamic programming approach based on state–space–time network representations," Transportation Research Part B: Methodological, Elsevier, vol. 89(C), pages 19-42.
    5. Raa, Birger & Aghezzaf, El-Houssaine, 2009. "A practical solution approach for the cyclic inventory routing problem," European Journal of Operational Research, Elsevier, vol. 192(2), pages 429-441, January.
    6. Ouyang, Yanfeng, 2007. "Design of vehicle routing zones for large-scale distribution systems," Transportation Research Part B: Methodological, Elsevier, vol. 41(10), pages 1079-1093, December.
    7. Zhao, Qiu-Hong & Chen, Shuang & Zang, Cun-Xun, 2008. "Model and algorithm for inventory/routing decision in a three-echelon logistics system," European Journal of Operational Research, Elsevier, vol. 191(3), pages 623-635, December.
    8. Ali Ekici & Okan Örsan Özener & Gültekin Kuyzu, 2015. "Cyclic Delivery Schedules for an Inventory Routing Problem," Transportation Science, INFORMS, vol. 49(4), pages 817-829, November.
    9. Park, Junhyuk & Tae, Hyunchul & Kim, Byung-In, 2012. "A post-improvement procedure for the mixed load school bus routing problem," European Journal of Operational Research, Elsevier, vol. 217(1), pages 204-213.
    10. Drexl, Andreas & Klose, Andreas, 2001. "Facility location models for distribution system design," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 546, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    11. Paweł Hanczar, 2014. "Solving IRP using location based heuristics," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 24(2), pages 81-96.
    12. Park, Junhyuk & Kim, Byung-In, 2010. "The school bus routing problem: A review," European Journal of Operational Research, Elsevier, vol. 202(2), pages 311-319, April.
    13. Lap Mui Ann Chan & M. Grazia Speranza & Luca Bertazzi, 2013. "Asymptotic analysis of periodic policies for the inventory routing problem," Naval Research Logistics (NRL), John Wiley & Sons, vol. 60(7), pages 525-540, October.
    14. Ali Ekici & Okan Örsan Özener, 2020. "Inventory routing for the last mile delivery of humanitarian relief supplies," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 42(3), pages 621-660, September.
    15. S. Michel & F. Vanderbeck, 2012. "A Column-Generation Based Tactical Planning Method for Inventory Routing," Operations Research, INFORMS, vol. 60(2), pages 382-397, April.
    16. 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.
    17. Emre Çankaya & Ali Ekici & Okan Örsan Özener, 2019. "Humanitarian relief supplies distribution: an application of inventory routing problem," Annals of Operations Research, Springer, vol. 283(1), pages 119-141, December.
    18. Aghezzaf, El-Houssaine & Raa, Birger & Van Landeghem, Hendrik, 2006. "Modeling inventory routing problems in supply chains of high consumption products," European Journal of Operational Research, Elsevier, vol. 169(3), pages 1048-1063, March.
    19. Perugia, Alessandro & Moccia, Luigi & Cordeau, Jean-François & Laporte, Gilbert, 2011. "Designing a home-to-work bus service in a metropolitan area," Transportation Research Part B: Methodological, Elsevier, vol. 45(10), pages 1710-1726.
    20. Irnich, Stefan & Laganà, Demetrio & Schlebusch, Claudia & Vocaturo, Francesca, 2015. "Two-phase branch-and-cut for the mixed capacitated general routing problem," European Journal of Operational Research, Elsevier, vol. 243(1), pages 17-29.

    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:oropre:v:46:y:1998:i:6:p:872-882. 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.