IDEAS home Printed from https://ideas.repec.org/a/wsi/apjorx/v26y2009i03ns0217595909002249.html
   My bibliography  Save this article

The Np-Hardness Of Minimizing The Total Late Work On An Unbounded Batch Machine

Author

Listed:
  • JIANFENG REN

    (College of Operations Research and Management Sciences, Qufu Normal University, Shangdong, 276826, China)

  • YUZHONG ZHANG

    (Department of Mathematics, Qufu Normal University, Shangdong, 276826, China)

  • GUO SUN

    (Department of Mathematics, Qufu Normal University, Shangdong, 276826, China)

Abstract

We consider the problem of minimizing the total late work$(\sum_{j=1}^{n}\, V_j)$on an unbounded batch processing machine, whereVj=min{Tj, pj}andTj=max{Cj- dj, 0}. The batch processing machine can process up toB (B ≥ n)jobs simultaneously. The jobs that are processed together form a batch, and all jobs in a batch start and complete at the same time, respectively. For a batch of jobs, the processing time of the batch is equal to the largest processing time among the jobs in this batch. In this paper, we prove that the problem$1|B \geq n|\sum_{j=1}^{n}V_j$is NP-hard.

Suggested Citation

  • Jianfeng Ren & Yuzhong Zhang & Guo Sun, 2009. "The Np-Hardness Of Minimizing The Total Late Work On An Unbounded Batch Machine," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 26(03), pages 351-363.
    • Handle: RePEc:wsi:apjorx:v:26:y:2009:i:03:n:s0217595909002249
    DOI: 10.1142/S0217595909002249
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0217595909002249
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S0217595909002249?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. Raymond Y. C. Tse & James R. Webb, 2003. "Models of Office Market Dynamics," Urban Studies, Urban Studies Journal Limited, vol. 40(1), pages 71-89, January.
    2. anonymous, 2003. "Bleak house: California yet to pass budget," Western economic developments, Federal Reserve Bank of San Francisco, issue Jun, pages 1-4.
    3. K-T Mak & A Ramaprasad, 2003. "Knowledge supply network," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 54(2), pages 175-183, February.
    4. John D. Burger & Stephen J. K. Walters, 2003. "Market Size, Pay, and Performance," Journal of Sports Economics, , vol. 4(2), pages 108-125, May.
    5. Unknown, 2003. "Michael Roberts and Nigel Key," Amber Waves:The Economics of Food, Farming, Natural Resources, and Rural America, United States Department of Agriculture, Economic Research Service, pages 1-1, February.
    6. anonymous, 2003. "Taking off: Discount airlines transform flying," EconSouth, Federal Reserve Bank of Atlanta, vol. 5(Q3), pages 8-13.
    7. Ucw, 2003. "Understanding Children's Work in Yemen," UCW Country Studies 3, Understanding Children's Work (UCW Programme).
    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. Xin Chen & Malgorzata Sterna & Xin Han & Jacek Blazewicz, 2016. "Scheduling on parallel identical machines with late work criterion: Offline and online cases," Journal of Scheduling, Springer, vol. 19(6), pages 729-736, December.
    2. Chen, Xin & Liang, Yage & Sterna, Małgorzata & Wang, Wen & Błażewicz, Jacek, 2020. "Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date," European Journal of Operational Research, Elsevier, vol. 284(1), pages 67-74.
    3. Sterna, Małgorzata, 2021. "Late and early work scheduling: A survey," Omega, Elsevier, vol. 104(C).
    4. Mosheiov, Gur & Oron, Daniel & Shabtay, Dvir, 2021. "Minimizing total late work on a single machine with generalized due-dates," European Journal of Operational Research, Elsevier, vol. 293(3), pages 837-846.
    5. Rubing Chen & Jinjiang Yuan & C.T. Ng & T.C.E. Cheng, 2019. "Single‐machine scheduling with deadlines to minimize the total weighted late work," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(7), pages 582-595, October.
    6. Sterna, Malgorzata, 2011. "A survey of scheduling problems with late work criteria," Omega, Elsevier, vol. 39(2), pages 120-129, April.
    7. Shang-Chia Liu & Jiahui Duan & Win-Chin Lin & Wen-Hsiang Wu & Jan-Yee Kung & Hau Chen & Chin-Chia Wu, 2018. "A Branch-and-Bound Algorithm for Two-Agent Scheduling with Learning Effect and Late Work Criterion," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(05), pages 1-24, October.

    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. Chang, Yuan-Chieh & Chen, Min-Nan, 2016. "Service regime and innovation clusters: An empirical study from service firms in Taiwan," Research Policy, Elsevier, vol. 45(9), pages 1845-1857.
    2. McClure, James & Kumcu, Erdogan, 2008. "Promotions and product pricing: Parsimony versus Veblenesque demand," Journal of Economic Behavior & Organization, Elsevier, vol. 65(1), pages 105-117, January.
    3. Huan Zhang & Lin Sun & Qiujie Zhang, 2022. "How Workplace Social Capital Affects Turnover Intention: The Mediating Role of Job Satisfaction and Burnout," IJERPH, MDPI, vol. 19(15), pages 1-12, August.
    4. Aniruddha Dutta, 2019. "Capacity Allocation of Game Tickets Using Dynamic Pricing," Data, MDPI, vol. 4(4), pages 1-12, October.
    5. Joshua M. Congdon-Hohman & Jonathan A. Lanning, 2018. "Beyond Moneyball," Journal of Sports Economics, , vol. 19(7), pages 1046-1061, October.
    6. Carlo Bellavite Pellegrini & Raul Caruso & Marco Di Domizio, 2021. "Relative wages, payroll structure and performance in soccer. Evidence from Italian Serie A (2007-2019)," DISCE - Quaderni del Dipartimento di Politica Economica dipe0015, Università Cattolica del Sacro Cuore, Dipartimenti e Istituti di Scienze Economiche (DISCE).
    7. John D. Burger & Stephen J. K. Walters, 2008. "The Existence and Persistence of a Winner's Curse: New Evidence from the (Baseball) Field," Southern Economic Journal, John Wiley & Sons, vol. 75(1), pages 232-245, July.
    8. Babatunde Buraimo & David Forrest & Robert Simmons, 2007. "Freedom of Entry, Market Size, and Competitive Outcome: Evidence from English Soccer," Southern Economic Journal, John Wiley & Sons, vol. 74(1), pages 204-213, July.
    9. Andrew Hughes & Cory Koedel & Joshua A. Price, 2015. "Positional WAR in the National Football League," Journal of Sports Economics, , vol. 16(6), pages 597-613, August.
    10. Raul Caruso & Marco Di Domizio & Domenico Rossignoli, 2017. "Aggregate wages of players and performance in Italian Serie A," Economia Politica: Journal of Analytical and Institutional Economics, Springer;Fondazione Edison, vol. 34(3), pages 515-531, December.
    11. Timothy C. Y. Chan & Justin A. Cho & David C. Novati, 2012. "Quantifying the Contribution of NHL Player Types to Team Performance," Interfaces, INFORMS, vol. 42(2), pages 131-145, April.
    12. Haupert, Michael & Murray, James, 2011. "Regime Switching and Wages in Major League Baseball under the Reserve Clause," MPRA Paper 29094, University Library of Munich, Germany.
    13. Marco Di Domizio & Carlo Bellavite Pellegrini & Raul Caruso, 2022. "Payroll dispersion and performance in soccer: A seasonal perspective analysis for Italian Serie A (2007–2021)," Contemporary Economic Policy, Western Economic Association International, vol. 40(3), pages 513-525, July.
    14. Cerchione, Roberto & Esposito, Emilio, 2016. "A systematic review of supply chain knowledge management research: State of the art and research opportunities," International Journal of Production Economics, Elsevier, vol. 182(C), pages 276-292.
    15. Richard Cebula & Christopher Coombs & Luther Lawson & Maggie Foley, 2013. "The Impacts of Promotions/Marketing, Scheduling, and Economic Factors on Total Gross Revenues for Minor League Baseball Teams," International Advances in Economic Research, Springer;International Atlantic Economic Society, vol. 19(3), pages 249-257, August.
    16. João V. Ferreira & Nobuyuki Hanaki & Benoît Tarroux, 2017. "On the Roots of the Intrinsic Value of Decision Rights: Evidence from France and Japan," Economics Working Paper Archive (University of Rennes & University of Caen) 2017-11, Center for Research in Economics and Management (CREM), University of Rennes, University of Caen and CNRS.
    17. Vicente Royuela & Roberto Gásquez, 2019. "On the Influence of Foreign Players on the Success of Football Clubs," Journal of Sports Economics, , vol. 20(5), pages 718-741, June.
    18. Daniela Vuri, 2010. "The Effect of Availability of School and Distance to School on Children's Time Allocation in Ghana," LABOUR, CEIS, vol. 24(s1), pages 46-75, December.
    19. Borooah Vani K & Mangan John E, 2010. "The "Bradman Class": An Exploration of Some Issues in the Evaluation of Batsmen for Test Matches, 1877-2006," Journal of Quantitative Analysis in Sports, De Gruyter, vol. 6(3), pages 1-21, July.
    20. Daniel Brown & Charles R. Link, 2008. "Population and Bandwagon Effects on Local Team Revenues in Major League Baseball," Journal of Sports Economics, , vol. 9(5), pages 470-487, October.

    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:wsi:apjorx:v:26:y:2009:i:03:n:s0217595909002249. 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: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/apjor/apjor.shtml .

    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.