IDEAS home Printed from https://ideas.repec.org/a/spr/aqjoor/v14y2016i2d10.1007_s10288-015-0299-2.html
   My bibliography  Save this article

Hierarchical optimization with double due dates on an unbounded parallel-batching machine to minimize maximum lateness

Author

Listed:
  • Cheng He

    (Henan University of Technology)

  • Hao Lin

    (Henan University of Technology)

Abstract

This paper studies a hierarchical optimization problem on an unbounded parallel-batching machine, in which two objective functions are maximum lateness induced by two sets of due dates, representing different purposes of two decision-makers. By a hierarchical optimization problem, we mean the problem of optimizing the secondary criterion under the constraint that the primary criterion is optimized. A parallel-batching machine is a machine that can handle several jobs in a batch in which all jobs start and complete respectively at the same time. We present an $$O(n\log P)$$ O ( n log P ) -time algorithm and an $$O(n^3)$$ O ( n 3 ) -time algorithm for this hierarchical scheduling problem, where P is the total processing time of all jobs.

Suggested Citation

  • Cheng He & Hao Lin, 2016. "Hierarchical optimization with double due dates on an unbounded parallel-batching machine to minimize maximum lateness," 4OR, Springer, vol. 14(2), pages 153-164, June.
    • Handle: RePEc:spr:aqjoor:v:14:y:2016:i:2:d:10.1007_s10288-015-0299-2
    DOI: 10.1007/s10288-015-0299-2
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10288-015-0299-2
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10288-015-0299-2?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. Hoogeveen, Han, 2005. "Multicriteria scheduling," European Journal of Operational Research, Elsevier, vol. 167(3), pages 592-623, December.
    2. He, Cheng & Lin, Yixun & Yuan, Jinjiang, 2010. "A note on the single machine scheduling to minimize the number of tardy jobs with deadlines," European Journal of Operational Research, Elsevier, vol. 201(3), pages 966-970, March.
    3. Allesandro Agnetis & Pitu B. Mirchandani & Dario Pacciarelli & Andrea Pacifici, 2004. "Scheduling Problems with Two Competing Agents," Operations Research, INFORMS, vol. 52(2), pages 229-242, April.
    4. Cheng He & Yixun Lin & Jinjiang Yuan, 2010. "Some Improved Algorithms On The Single Machine Hierarchical Scheduling With Total Tardiness As The Primary Criterion," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 27(05), pages 577-585.
    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. Jinjiang Yuan, 2017. "Unary NP-hardness of minimizing the number of tardy jobs with deadlines," Journal of Scheduling, Springer, vol. 20(2), pages 211-218, April.
    2. Balasubramanian, Hari & Fowler, John & Keha, Ahmet & Pfund, Michele, 2009. "Scheduling interfering job sets on parallel machines," European Journal of Operational Research, Elsevier, vol. 199(1), pages 55-67, November.
    3. Zhichao Geng & Jiayu Liu, 0. "Single machine batch scheduling with two non-disjoint agents and splitable jobs," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-22.
    4. Qiulan Zhao & Jinjiang Yuan, 2020. "Bicriteria scheduling of equal length jobs on uniform parallel machines," Journal of Combinatorial Optimization, Springer, vol. 39(3), pages 637-661, April.
    5. Cheng He & Joseph Y.-T. Leung, 2017. "Two-agent scheduling of time-dependent jobs," Journal of Combinatorial Optimization, Springer, vol. 34(2), pages 362-377, August.
    6. Shi-Sheng Li & Ren-Xia Chen, 2023. "Competitive two-agent scheduling with release dates and preemption on a single machine," Journal of Scheduling, Springer, vol. 26(3), pages 227-249, June.
    7. Chen, Rubing & Geng, Zhichao & Lu, Lingfa & Yuan, Jinjiang & Zhang, Yuan, 2022. "Pareto-scheduling of two competing agents with their own equal processing times," European Journal of Operational Research, Elsevier, vol. 301(2), pages 414-431.
    8. Zhichao Geng & Jiayu Liu, 2020. "Single machine batch scheduling with two non-disjoint agents and splitable jobs," Journal of Combinatorial Optimization, Springer, vol. 40(3), pages 774-795, October.
    9. Wan, Long & Yuan, Jinjiang & Wei, Lijun, 2016. "Pareto optimization scheduling with two competing agents to minimize the number of tardy jobs and the maximum cost," Applied Mathematics and Computation, Elsevier, vol. 273(C), pages 912-923.
    10. Jiang, Xiaojuan & Lee, Kangbok & Pinedo, Michael L., 2023. "Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time," European Journal of Operational Research, Elsevier, vol. 305(2), pages 594-607.
    11. Perez-Gonzalez, Paz & Framinan, Jose M., 2014. "A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems," European Journal of Operational Research, Elsevier, vol. 235(1), pages 1-16.
    12. Chen, Rubing & Yuan, Jinjiang & Ng, C.T. & Cheng, T.C.E., 2021. "Single-machine hierarchical scheduling with release dates and preemption to minimize the total completion time and a regular criterion," European Journal of Operational Research, Elsevier, vol. 293(1), pages 79-92.
    13. Wan, Long & Ding, Zhihao & Li, Yunpeng & Chen, Qianqian & Tan, Zhiyi, 2015. "Scheduling to minimize the maximum total completion time per machine," European Journal of Operational Research, Elsevier, vol. 242(1), pages 45-50.
    14. Lee, Kangbok & Leung, Joseph Y-T. & Jia, Zhao-hong & Li, Wenhua & Pinedo, Michael L. & Lin, Bertrand M.T., 2014. "Fast approximation algorithms for bi-criteria scheduling with machine assignment costs," European Journal of Operational Research, Elsevier, vol. 238(1), pages 54-64.
    15. Byung-Cheon Choi & Myoung-Ju Park, 2015. "A Batch Scheduling Problem with Two Agents," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 32(06), pages 1-19, December.
    16. Shi-Sheng Li & Ren-Xia Chen & Qi Feng, 2016. "Scheduling two job families on a single machine with two competitive agents," Journal of Combinatorial Optimization, Springer, vol. 32(3), pages 784-799, October.
    17. David Fischer & Péter Györgyi, 2023. "Approximation algorithms for coupled task scheduling minimizing the sum of completion times," Annals of Operations Research, Springer, vol. 328(2), pages 1387-1408, September.
    18. Adhau, Sunil & Mittal, M.L. & Mittal, Abhinav, 2013. "A multi-agent system for decentralized multi-project scheduling with resource transfers," International Journal of Production Economics, Elsevier, vol. 146(2), pages 646-661.
    19. 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.
    20. Wen-Hung Wu & Yunqiang Yin & T C E Cheng & Win-Chin Lin & Juei-Chao Chen & Shin-Yi Luo & Chin-Chia Wu, 2017. "A combined approach for two-agent scheduling with sum-of-processing-times-based learning effect," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(2), pages 111-120, February.

    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:spr:aqjoor:v:14:y:2016:i:2:d:10.1007_s10288-015-0299-2. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.