IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v233y2014i1p75-83.html
   My bibliography  Save this article

Optimal single machine scheduling of products with components and changeover cost

Author

Listed:
  • Zhou, Feng
  • Blocher, James D.
  • Hu, Xinxin
  • Sebastian Heese, H.

Abstract

We consider the problem of scheduling products with components on a single machine, where changeovers incur fixed costs. The objective is to minimize the weighted sum of total flow time and changeover cost. We provide properties of optimal solutions and develop an explicit characterization of optimal sequences, while showing that this characterization has recurrent properties. Our structural results have interesting implications for practitioners, primarily that the structure of optimal sequences is robust to changes in demand.

Suggested Citation

  • Zhou, Feng & Blocher, James D. & Hu, Xinxin & Sebastian Heese, H., 2014. "Optimal single machine scheduling of products with components and changeover cost," European Journal of Operational Research, Elsevier, vol. 233(1), pages 75-83.
    • Handle: RePEc:eee:ejores:v:233:y:2014:i:1:p:75-83
    DOI: 10.1016/j.ejor.2013.08.016
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221713006814
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2013.08.016?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Lin, Bertrand M. T., 2002. "Fabrication scheduling on a single machine with due date constraints," European Journal of Operational Research, Elsevier, vol. 136(1), pages 95-105, January.
    2. Cheng, T.C.E. & Ng, C.T. & Yuan, J.J., 2008. "Single-machine scheduling of multi-operation jobs without missing operations to minimize the total completion time," European Journal of Operational Research, Elsevier, vol. 191(2), pages 320-331, December.
    3. Mosheiov, Gur & Oron, Daniel, 2008. "A single machine batch scheduling problem with bounded batch size," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1069-1079, June.
    4. Bongjin Gim & Min-Hong Han, 1997. "Economic scheduling of products with N components on a single machine," European Journal of Operational Research, Elsevier, vol. 96(3), pages 570-577, February.
    5. 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.
    6. Kovalyov, M. Y. & Potts, C. N. & Strusevich, V. A., 2004. "Batching decisions for assembly production systems," European Journal of Operational Research, Elsevier, vol. 157(3), pages 620-642, September.
    7. Gregory Dobson & Uday S. Karmarkar & Jeffrey L. Rummel, 1987. "Batching to Minimize Flow Times on One Machine," Management Science, INFORMS, vol. 33(6), pages 784-799, June.
    8. T. L. Magnanti & R. Vachani, 1990. "A Strong Cutting Plane Algorithm for Production Scheduling with Changeover Costs," Operations Research, INFORMS, vol. 38(3), pages 456-473, June.
    9. T.C. Cheng & Mikhail Kovalyov, 2001. "Single Supplier Scheduling for Multiple Deliveries," Annals of Operations Research, Springer, vol. 107(1), pages 51-63, October.
    10. 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.
    11. Gerodimos, Alex E. & Glass, Celia A. & Potts, Chris N., 2000. "Scheduling the production of two-component jobs on a single machine," European Journal of Operational Research, Elsevier, vol. 120(2), pages 250-259, January.
    12. B. Lin & T. Cheng, 2005. "Two-Machine Flowshop Batching and Scheduling," Annals of Operations Research, Springer, vol. 133(1), pages 149-161, January.
    13. Edward G. Coffman & Ardavan Nozari & Mihalis Yannakakis, 1989. "Optimal Scheduling of Products with Two Subassemblies on a Single Machine," Operations Research, INFORMS, vol. 37(3), pages 426-436, June.
    14. Offer Kella, 1991. "Optimal Manufacturing of a Two Product Mix," Operations Research, INFORMS, vol. 39(3), pages 496-501, June.
    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. Kozlovskaya, Nadezhda & Pakhomova, Nadezhda & Richter, Knut, 2016. "A general production and recovery EOQ model with stationary demand and return rates," Discussion Papers 378, European University Viadrina Frankfurt (Oder), Department of Business Administration and Economics.

    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. Xinxin Hu & James D Blocher & Hans Sebastian Heese & Feng Zhou, 2016. "Scheduling products with subassemblies and changeover time," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(8), pages 1025-1033, August.
    2. 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.
    3. Grundel, Soesja & Çiftçi, Barış & Borm, Peter & Hamers, Herbert, 2013. "Family sequencing and cooperation," European Journal of Operational Research, Elsevier, vol. 226(3), pages 414-424.
    4. F. Hwang & M. Kovalyov & B. Lin, 2014. "Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence," Annals of Operations Research, Springer, vol. 217(1), pages 263-279, June.
    5. Lele Zhang & Andrew Wirth, 2010. "On-line machine scheduling with batch setups," Journal of Combinatorial Optimization, Springer, vol. 20(3), pages 285-306, October.
    6. Mosheiov, Gur & Oron, Daniel, 2008. "A single machine batch scheduling problem with bounded batch size," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1069-1079, June.
    7. Yoon, Sang Hum & Sung, Chang Sup, 2005. "Fixed pre-assembly scheduling on multiple fabrication machines," International Journal of Production Economics, Elsevier, vol. 96(1), pages 109-118, April.
    8. Gur Mosheiov & Daniel Oron & Yaacov Ritov, 2004. "Flow‐shop batch scheduling with identical processing‐time jobs," Naval Research Logistics (NRL), John Wiley & Sons, vol. 51(6), pages 783-799, September.
    9. Liji Shen & Lars Mönch & Udo Buscher, 2013. "An iterative approach for the serial batching problem with parallel machines and job families," Annals of Operations Research, Springer, vol. 206(1), pages 425-448, July.
    10. Yijie Li, 2023. "Bicriteria fabrication scheduling of two-component jobs on a single machine," Operational Research, Springer, vol. 23(4), pages 1-13, December.
    11. A. Dolgui & M. Kovalyov & K. Shchamialiova, 2011. "Multi-product lot-sizing and sequencing on a single imperfect machine," Computational Optimization and Applications, Springer, vol. 50(3), pages 465-482, December.
    12. 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.
    13. Dolgui, Alexandre & Hashemi-Petroodi, S. Ehsan & Kovalev, Sergey & Kovalyov, Mikhail Y., 2021. "Profitability of a multi-model manufacturing line versus multiple dedicated lines," International Journal of Production Economics, Elsevier, vol. 236(C).
    14. Mor, Baruch & Mosheiov, Gur, 2014. "Batch scheduling with a rate-modifying maintenance activity to minimize total flowtime," International Journal of Production Economics, Elsevier, vol. 153(C), pages 238-242.
    15. Lele Zhang & Andrew Wirth, 2016. "Online Machine Scheduling with Family Setups," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(04), pages 1-16, August.
    16. Florian Jaehn & Sergey Kovalev & Mikhail Y. Kovalyov & Erwin Pesch, 2014. "Multiproduct batching and scheduling with buffered rework: The case of a car paint shop," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(6), pages 458-471, September.
    17. Dolgui, Alexandre & Kovalev, Sergey & Kovalyov, Mikhail Y. & Nossack, Jenny & Pesch, Erwin, 2014. "Minimizing setup costs in a transfer line design problem with sequential operation processing," International Journal of Production Economics, Elsevier, vol. 151(C), pages 186-194.
    18. Jinwen Ou, 2020. "Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection," Journal of Scheduling, Springer, vol. 23(5), pages 525-538, October.
    19. Pang, King-Wah, 2013. "A genetic algorithm based heuristic for two machine no-wait flowshop scheduling problems with class setup times that minimizes maximum lateness," International Journal of Production Economics, Elsevier, vol. 141(1), pages 127-136.
    20. Gribkovskaia, Irina V. & Kovalev, Sergey & Werner, Frank, 2010. "Batching for work and rework processes on dedicated facilities to minimize the makespan," Omega, Elsevier, vol. 38(6), pages 522-527, December.

    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:eee:ejores:v:233:y:2014:i:1:p:75-83. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.