IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v61y2010i1d10.1057_jors.2008.148.html
   My bibliography  Save this article

A dispatching algorithm for parallel machines with rework processes

Author

Listed:
  • Y H Kang

    (North Carolina State University)

  • S S Kim

    (Korea Univeristy)

  • H J Shin

    () (Sangmyung University)

Abstract

This paper presents a parallel machine scheduling problem with rework probabilities, due-dates and sequence-dependent setup times. It is assumed that rework probability for each job on a machine can be given through historical data acquisition. Since the problem is NP-hard in the strong sense, a heuristic algorithm is presented, which finds good solutions. The dispatching algorithm named MRPD (minimum rework probability with due-dates) is proposed in this paper focusing on the rework processes. The performance of MRPD is measured by the six diagnostic indicators: total tardiness, maximum lateness, mean flow-time, mean lateness, the number of reworks and the number of tardy jobs. A large number of test problems are randomly generated to evaluate the performance of the proposed algorithm. Computational results show that the proposed algorithm is significantly superior to existing dispatching algorithms for the test problems.

Suggested Citation

  • Y H Kang & S S Kim & H J Shin, 2010. "A dispatching algorithm for parallel machines with rework processes," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 61(1), pages 144-155, January.
  • Handle: RePEc:pal:jorsoc:v:61:y:2010:i:1:d:10.1057_jors.2008.148
    DOI: 10.1057/jors.2008.148
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/jors.2008.148
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.

    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. Hau L. Lee, 1992. "Lot Sizing to Reduce Capacity Utilization in a Production Process with Defective Items, Process Corrections, and Rework," Management Science, INFORMS, vol. 38(9), pages 1314-1328, September.
    2. Agnihothri, Saligrama R. & Kenett, Ron S., 1995. "The impact of defects on a process with rework," European Journal of Operational Research, Elsevier, vol. 80(2), pages 308-327, January.
    3. Lee, Young Hoon & Pinedo, Michael, 1997. "Scheduling jobs on parallel machines with sequence-dependent setup times," European Journal of Operational Research, Elsevier, vol. 100(3), pages 464-474, August.
    4. Liu, John J. & Yang, Ping, 1996. "Optimal lot-sizing in an imperfect production system with homogeneous reworkable jobs," European Journal of Operational Research, Elsevier, vol. 91(3), pages 517-527, June.
    5. Flapper, Simme Douwe P. & Teunter, Ruud H., 2004. "Logistic planning of rework with deteriorating work-in-process," International Journal of Production Economics, Elsevier, vol. 88(1), pages 51-59, March.
    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. 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.
    2. Yuan-Shyi Peter Chiu & Chih-An Katherine Lin & Huei-Hsin Chang & Victoria Chiu, 2010. "Mathematical modelling for determining economic batch size and optimal number of deliveries for EPQ model with quality assurance," Mathematical and Computer Modelling of Dynamical Systems, Taylor & Francis Journals, vol. 16(4), pages 373-388, July.
    3. Sarker, Bhaba R. & Jamal, A.M.M. & Mondal, Sanjay, 2008. "Optimal batch sizing in a multi-stage production system with rework consideration," European Journal of Operational Research, Elsevier, vol. 184(3), pages 915-929, February.
    4. Flapper, Simme Douwe P. & Teunter, Ruud H., 2004. "Logistic planning of rework with deteriorating work-in-process," International Journal of Production Economics, Elsevier, vol. 88(1), pages 51-59, March.
    5. Michele Ciavotta & Carlo Meloni & Marco Pranzo, 2016. "Speeding up a Rollout algorithm for complex parallel machine scheduling," International Journal of Production Research, Taylor & Francis Journals, vol. 54(16), pages 4993-5009, August.
    6. Sesh Murthy & Rama Akkiraju & Richard Goodwin & Pinar Keskinocak & John Rachlin & Frederick Wu & James Yeh & Robert Fuhrer & Santhosh Kumaran & Alok Aggarwal & Martin Sturzenbecker & Ranga Jayaraman &, 1999. "Cooperative Multiobjective Decision Support for the Paper Industry," Interfaces, INFORMS, vol. 29(5), pages 5-30, October.
    7. Jaber, Mohamad Y. & Guiffrida, Alfred L., 2008. "Learning curves for imperfect production processes with reworks and process restoration interruptions," European Journal of Operational Research, Elsevier, vol. 189(1), pages 93-104, August.
    8. Oner, Selma & Bilgic, Taner, 2008. "Economic lot scheduling with uncontrolled co-production," European Journal of Operational Research, Elsevier, vol. 188(3), pages 793-810, August.
    9. Alidaee, Bahram & Kochenberger, Gary A. & Amini, Mohammad M., 2001. "Greedy solutions of selection and ordering problems," European Journal of Operational Research, Elsevier, vol. 134(1), pages 203-215, October.
    10. K-L Hou, 2005. "Optimal production run length for deteriorating production system with a two-state continuous-time Markovian processes under allowable shortages," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 56(3), pages 346-350, March.
    11. S-O Shim & Y-D Kim, 2007. "Minimizing total tardiness in an unrelated parallel-machine scheduling problem," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(3), pages 346-354, March.
    12. Andrew Lim & Brian Rodrigues & Zhou Xu, 2007. "A m‐parallel crane scheduling problem with a non‐crossing constraint," Naval Research Logistics (NRL), John Wiley & Sons, vol. 54(2), pages 115-127, March.
    13. Hauck, Zsuzsanna & Vörös, József, 2015. "Lot sizing in case of defective items with investments to increase the speed of quality control," Omega, Elsevier, vol. 52(C), pages 180-189.
    14. Al-Anzi, Fawaz S. & Allahverdi, Ali & Kovalyov, Mikhail Y., 2007. "Batching deteriorating items with applications in computer communication and reverse logistics," European Journal of Operational Research, Elsevier, vol. 182(3), pages 1002-1011, November.
    15. Ouyang, Liang-Yuh & Chang, Chun-Tao, 2013. "Optimal production lot with imperfect production process under permissible delay in payments and complete backlogging," International Journal of Production Economics, Elsevier, vol. 144(2), pages 610-617.
    16. Chiu, Singa Wang, 2008. "Production lot size problem with failure in repair and backlogging derived without derivatives," European Journal of Operational Research, Elsevier, vol. 188(2), pages 610-615, July.
    17. Al-Salamah, Muhammad, 2019. "Economic production quantity in an imperfect manufacturing process with synchronous and asynchronous flexible rework rates," Operations Research Perspectives, Elsevier, vol. 6(C).
    18. Barad, M. & Bennett, G., 1996. "Optimal yield improvement in multi-stage manufacturing systems," European Journal of Operational Research, Elsevier, vol. 95(3), pages 549-565, December.
    19. Jinfa Chen & David D. Yao & Shaohui Zheng, 2001. "Optimal Replenishment and Rework with Multiple Unreliable Supply Sources," Operations Research, INFORMS, vol. 49(3), pages 430-443, June.
    20. Nita H. Shah & Dushyantkumar G. Patel & Digeshkumar B. Shah, 2018. "EPQ model for returned/reworked inventories during imperfect production process under price-sensitive stock-dependent demand," Operational Research, Springer, vol. 18(2), pages 343-359, July.

    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:pal:jorsoc:v:61:y:2010:i:1:d:10.1057_jors.2008.148. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Sonal Shukla) or (Springer Nature Abstracting and Indexing). General contact details of provider: http://www.palgrave-journals.com/ .

    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 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.

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.