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

Polynomial‐time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time

Author

Listed:
  • T.C. Edwin Cheng
  • Qingqin Nong
  • Chi To Ng

Abstract

In this article, we consider the concurrent open shop scheduling problem to minimize the total weighted completion time. When the number of machines is arbitrary, the problem has been shown to be inapproximable within a factor of 4/3 ‐ ε for any ε > 0 if the unique games conjecture is true in the literature. We propose a polynomial time approximation scheme for the problem under the restriction that the number of machines is fixed. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011

Suggested Citation

  • T.C. Edwin Cheng & Qingqin Nong & Chi To Ng, 2011. "Polynomial‐time approximation scheme for concurrent open shop scheduling with a fixed number of machines to minimize the total weighted completion time," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(8), pages 763-770, December.
    • Handle: RePEc:wly:navres:v:58:y:2011:i:8:p:763-770
    DOI: 10.1002/nav.20484
    as

    Download full text from publisher

    File URL: https://doi.org/10.1002/nav.20484
    Download Restriction: no
    File URL: https://libkey.io/10.1002/nav.20484?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. Chang Sup Sung & Sang Hum Yoon, 1998. "Minimizing total weighted completion time at a pre-assembly stage composed of two feeding machines," International Journal of Production Economics, Elsevier, vol. 54(3), pages 247-255, May.
    2. Leung, Joseph Y.-T. & Li, Haibing & Pinedo, Michael, 2006. "Scheduling orders for multiple product types with due date related objectives," European Journal of Operational Research, Elsevier, vol. 168(2), pages 370-389, January.
    3. Wagneur, E. & Sriskandarajah, C., 1993. "Openshops with jobs overlap," European Journal of Operational Research, Elsevier, vol. 71(3), pages 366-378, December.
    4. Reza Ahmadi & Uttarayan Bagchi & Thomas A. Roemer, 2005. "Coordinated scheduling of customer orders for quick response," Naval Research Logistics (NRL), John Wiley & Sons, vol. 52(6), pages 493-512, September.
    5. Wayne E. Smith, 1956. "Various optimizers for single‐stage production," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 3(1‐2), pages 59-66, 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. Framinan, Jose M. & Perez-Gonzalez, Paz & Fernandez-Viagas, Victor, 2019. "Deterministic assembly scheduling problems: A review and classification of concurrent-type scheduling models and solution procedures," European Journal of Operational Research, Elsevier, vol. 273(2), pages 401-417.
    2. Ren-Xia Chen & Shi-Sheng Li, 2020. "Minimizing maximum delivery completion time for order scheduling with rejection," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 1044-1064, November.
    3. Lung-Yu Li & Jian-You Xu & Shuenn-Ren Cheng & Xingong Zhang & Win-Chin Lin & Jia-Cheng Lin & Zong-Lin Wu & Chin-Chia Wu, 2022. "A Genetic Hyper-Heuristic for an Order Scheduling Problem with Two Scenario-Dependent Parameters in a Parallel-Machine Environment," Mathematics, MDPI, vol. 10(21), pages 1-22, November.
    4. Leung, Joseph Y-T. & Li, Haibing & Pinedo, Michael & Sriskandarajah, Chelliah, 2005. "Open shops with jobs overlap--revisited," European Journal of Operational Research, Elsevier, vol. 163(2), pages 569-571, June.
    5. Joseph Leung & Haibing Li & Michael Pinedo, 2008. "Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time," Annals of Operations Research, Springer, vol. 159(1), pages 107-123, March.
    6. Framinan, Jose M. & Perez-Gonzalez, Paz, 2018. "Order scheduling with tardiness objective: Improved approximate solutions," European Journal of Operational Research, Elsevier, vol. 266(3), pages 840-850.
    7. Wang, Guoqing & Cheng, T.C. Edwin, 2007. "Customer order scheduling to minimize total weighted completion time," Omega, Elsevier, vol. 35(5), pages 623-626, October.
    8. B. M. T. Lin & T. C. E. Cheng, 2011. "Scheduling with centralized and decentralized batching policies in concurrent open shops," Naval Research Logistics (NRL), John Wiley & Sons, vol. 58(1), pages 17-27, February.
    9. Lee, Ik Sun, 2013. "Minimizing total tardiness for the order scheduling problem," International Journal of Production Economics, Elsevier, vol. 144(1), pages 128-134.
    10. Leung, Joseph Y.-T. & Li, Haibing & Pinedo, Michael, 2006. "Scheduling orders for multiple product types with due date related objectives," European Journal of Operational Research, Elsevier, vol. 168(2), pages 370-389, January.
    11. Fernandez-Viagas, Victor & Talens, Carla & Framinan, Jose M., 2022. "Assembly flowshop scheduling problem: Speed-up procedure and computational evaluation," European Journal of Operational Research, Elsevier, vol. 299(3), pages 869-882.
    12. Leung, Joseph Y.-T. & Lee, C.Y. & Ng, C.W. & Young, G.H., 2008. "Preemptive multiprocessor order scheduling to minimize total weighted flowtime," European Journal of Operational Research, Elsevier, vol. 190(1), pages 40-51, October.
    13. Lin, B.M.T. & Kononov, A.V., 2007. "Customer order scheduling to minimize the number of late jobs," European Journal of Operational Research, Elsevier, vol. 183(2), pages 944-948, December.
    14. Joseph Y‐T. Leung & Haibing Li & Michael Pinedo, 2006. "Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(4), pages 243-260, June.
    15. Marieke Quant & Marc Meertens & Hans Reijnierse, 2008. "Processing games with shared interest," Annals of Operations Research, Springer, vol. 158(1), pages 219-228, February.
    16. José R. Correa & Maurice Queyranne, 2012. "Efficiency of equilibria in restricted uniform machine scheduling with total weighted completion time as social cost," Naval Research Logistics (NRL), John Wiley & Sons, vol. 59(5), pages 384-395, August.
    17. Ben Hermans & Roel Leus & Jannik Matuschke, 2022. "Exact and Approximation Algorithms for the Expanding Search Problem," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 281-296, January.
    18. Qiuping Yu & Gad Allon & Achal Bassamboo & Seyed Iravani, 2018. "Managing Customer Expectations and Priorities in Service Systems," Management Science, INFORMS, vol. 64(8), pages 3942-3970, August.
    19. Lili Liu & Guochun Tang & Baoqiang Fan & Xingpeng Wang, 2015. "Two-person cooperative games on scheduling problems in outpatient pharmacy dispensing process," Journal of Combinatorial Optimization, Springer, vol. 30(4), pages 938-948, November.
    20. van Beek, Andries & Malmberg, Benjamin & Borm, Peter & Quant, Marieke & Schouten, Jop, 2021. "Cooperation and Competition in Linear Production and Sequencing Processes," Discussion Paper 2021-011, Tilburg University, Center for Economic Research.

    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:58:y:2011:i:8:p:763-770. 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.