IDEAS home Printed from https://ideas.repec.org/a/wly/navres/v55y2008i7p654-669.html
   My bibliography  Save this article

Scheduling multiple products on parallel machines with setup costs

Author

Listed:
  • Vladimir Krasik
  • Joseph Leung
  • Michael Pinedo
  • Jiawei Zhang

Abstract

We consider a class of production scheduling models with m identical machines in parallel and k different product types. It takes a time pi to produce one unit of product type i on any one of the machines. There is a demand stream for product type i consisting of ni units with each unit having a given due date. Before a machine starts with the production of a batch of products of type i a setup cost c is is incurred. We consider several different objective functions. Each one of the objective functions has three components, namely a total setup cost, a total earliness cost, and a total tardiness cost. In our class of problems we find a relatively large number of problems that can be solved either in polynomial time or in pseudo‐polynomial time. The polynomiality or pseudo‐polynomiality is achieved under certain special conditions that may be of practical interest; for example, a regularity pattern in the string of due dates combined with earliness and tardiness costs that are similar for different types of products. The class of models we consider includes as special cases discrete counterparts of a number of inventory models that have been considered in the literature before, e.g., Wagner and Whitin (Manage Sci 5 (1958), 89–96) and Zangwill (Oper Res 14 (1966), 486–507; Manage Sci 15 (1969), 506–527). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008

Suggested Citation

  • Vladimir Krasik & Joseph Leung & Michael Pinedo & Jiawei Zhang, 2008. "Scheduling multiple products on parallel machines with setup costs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(7), pages 654-669, October.
    • Handle: RePEc:wly:navres:v:55:y:2008:i:7:p:654-669
    DOI: 10.1002/nav.20309
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.20309
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.20309?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. Albert Wagelmans & Stan van Hoesel & Antoon Kolen, 1992. "Economic Lot Sizing: An O(n log n) Algorithm That Runs in Linear Time in the Wagner-Whitin Case," Operations Research, INFORMS, vol. 40(1-supplem), pages 145-156, February.
    2. Gregory Dobson, 1987. "The Economic Lot-Scheduling Problem: Achieving Feasibility Using Time-Varying Lot Sizes," Operations Research, INFORMS, vol. 35(5), pages 764-771, October.
    3. Harvey M. Wagner & Thomson M. Whitin, 1958. "Dynamic Version of the Economic Lot Size Model," Management Science, INFORMS, vol. 5(1), pages 89-96, October.
    4. Willard I. Zangwill, 1966. "A Deterministic Multiproduct, Multi-Facility Production and Inventory Model," Operations Research, INFORMS, vol. 14(3), pages 486-507, June.
    5. Zhi-Long Chen, 1997. "Scheduling with batch setup times and earliness-tardiness penalties," European Journal of Operational Research, Elsevier, vol. 96(3), pages 518-537, February.
    6. Willard I. Zangwill, 1968. "Minimum Concave Cost Flows in Certain Networks," Management Science, INFORMS, vol. 14(7), pages 429-450, March.
    7. Kenneth R. Baker & Gary D. Scudder, 1990. "Sequencing with Earliness and Tardiness Penalties: A Review," Operations Research, INFORMS, vol. 38(1), pages 22-36, February.
    8. Gregory Dobson, 1992. "The Cyclic Lot Scheduling Problem with Sequence-Dependent Setups," Operations Research, INFORMS, vol. 40(4), pages 736-749, August.
    9. Marc Salomon & Leo G. Kroon & Roelof Kuik & Luk N. Van Wassenhove, 1991. "Some Extensions of the Discrete Lotsizing and Scheduling Problem," Management Science, INFORMS, vol. 37(7), pages 801-812, July.
    10. Gabrel, Virginie, 1995. "Scheduling jobs within time windows on identical parallel machines: New model and algorithms," European Journal of Operational Research, Elsevier, vol. 83(2), pages 320-329, June.
    11. Jeremy F. Shapiro, 2001. "Modeling and IT Perspectives on Supply Chain Integration," Information Systems Frontiers, Springer, vol. 3(4), pages 455-464, December.
    12. Drexl, A. & Kimms, A., 1997. "Lot sizing and scheduling -- Survey and extensions," European Journal of Operational Research, Elsevier, vol. 99(2), pages 221-235, June.
    13. Potts, Chris N. & Kovalyov, Mikhail Y., 2000. "Scheduling with batching: A review," European Journal of Operational Research, Elsevier, vol. 120(2), pages 228-249, January.
    14. Scott Webster & Kenneth R. Baker, 1995. "Scheduling Groups of Jobs on a Single Machine," Operations Research, INFORMS, vol. 43(4), pages 692-703, August.
    15. Cheng, T. C. Edwin & Janiak, Adam & Kovalyov, Mikhail Y., 2001. "Single machine batch scheduling with resource dependent setup and processing times," European Journal of Operational Research, Elsevier, vol. 135(1), pages 177-183, November.
    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. Huiqiao Su & Michael Pinedo & Guohua Wan, 2017. "Parallel machine scheduling with eligibility constraints: A composite dispatching rule to minimize total weighted tardiness," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(3), pages 249-267, April.

    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. Hark-Chin Hwang & Hyun-Soo Ahn & Philip Kaminsky, 2013. "Basis Paths and a Polynomial Algorithm for the Multistage Production-Capacitated Lot-Sizing Problem," Operations Research, INFORMS, vol. 61(2), pages 469-482, April.
    2. Jans, Raf & Degraeve, Zeger, 2007. "Meta-heuristics for dynamic lot sizing: A review and comparison of solution approaches," European Journal of Operational Research, Elsevier, vol. 177(3), pages 1855-1875, March.
    3. Drexl, Andreas & Haase, Knut, 1992. "A new type of model for multi-item capacitated dynamic lotsizing and scheduling," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 286, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    4. Carsten Jordan & Andreas Drexl, 1998. "Discrete Lotsizing and Scheduling by Batch Sequencing," Management Science, INFORMS, vol. 44(5), pages 698-713, May.
    5. Wolosewicz, Cathy & Dauzère-Pérès, Stéphane & Aggoune, Riad, 2015. "A Lagrangian heuristic for an integrated lot-sizing and fixed scheduling problem," European Journal of Operational Research, Elsevier, vol. 244(1), pages 3-12.
    6. Fowler, John W. & Mönch, Lars, 2022. "A survey of scheduling with parallel batch (p-batch) processing," European Journal of Operational Research, Elsevier, vol. 298(1), pages 1-24.
    7. Hark‐Chin Hwang & Wilco van den Heuvel, 2012. "Improved algorithms for a lot‐sizing problem with inventory bounds and backlogging," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(3‐4), pages 244-253, April.
    8. Martel, Alain & Gascon, Andre, 1998. "Dynamic lot-sizing with price changes and price-dependent holding costs," European Journal of Operational Research, Elsevier, vol. 111(1), pages 114-128, November.
    9. Vernon Ning Hsu, 2000. "Dynamic Economic Lot Size Model with Perishable Inventory," Management Science, INFORMS, vol. 46(8), pages 1159-1169, August.
    10. Selvarajah, Esaignani & Steiner, George, 2006. "Batch scheduling in a two-level supply chain--a focus on the supplier," European Journal of Operational Research, Elsevier, vol. 173(1), pages 226-240, August.
    11. Sanja Petrovic & Carole Fayad & Dobrila Petrovic & Edmund Burke & Graham Kendall, 2008. "Fuzzy job shop scheduling with lot-sizing," Annals of Operations Research, Springer, vol. 159(1), pages 275-292, March.
    12. Fink, Jiří & Hurink, Johann L., 2015. "Minimizing costs is easier than minimizing peaks when supplying the heat demand of a group of houses," European Journal of Operational Research, Elsevier, vol. 242(2), pages 644-650.
    13. Drexl, Andreas & Jordan, Carsten & Kimms, Alf, 1997. "Gruppierungs- und Reihenfolgeprobleme in der Fertigung," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 447, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    14. Hwang, Hark-Chin & Jaruphongsa, Wikrom, 2008. "Dynamic lot-sizing model for major and minor demands," European Journal of Operational Research, Elsevier, vol. 184(2), pages 711-724, January.
    15. Karimi, B. & Fatemi Ghomi, S. M. T. & Wilson, J. M., 2003. "The capacitated lot sizing problem: a review of models and algorithms," Omega, Elsevier, vol. 31(5), pages 365-378, October.
    16. Otto, Alena & Li, Xiyu, 2020. "Product sequencing in multiple-piece-flow assembly lines," Omega, Elsevier, vol. 91(C).
    17. Eksioglu, Sandra Duni, 2009. "A primal-dual algorithm for the economic lot-sizing problem with multi-mode replenishment," European Journal of Operational Research, Elsevier, vol. 197(1), pages 93-101, August.
    18. Allahverdi, Ali & Ng, C.T. & Cheng, T.C.E. & Kovalyov, Mikhail Y., 2008. "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, Elsevier, vol. 187(3), pages 985-1032, June.
    19. Hwang, Hark-Chin & Kang, Jangha, 2021. "An improved algorithm for the lot-sizing problem with outbound shipment," Omega, Elsevier, vol. 100(C).
    20. Shisheng Li & T.C.E. Cheng & C.T. Ng & Jinjiang Yuan, 2017. "Two‐agent scheduling on a single sequential and compatible batching machine," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(8), pages 628-641, December.

    More about this item

    Statistics

    Access and download statistics

    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:wly:navres:v:55:y:2008:i:7:p:654-669. 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: Wiley Content Delivery (email available below). General contact details of provider: https://doi.org/10.1002/(ISSN)1520-6750 .

    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.