IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v199y2009i1p55-67.html

Scheduling interfering job sets on parallel machines

Author

Listed:
  • Balasubramanian, Hari
  • Fowler, John
  • Keha, Ahmet
  • Pfund, Michele

Abstract

We consider bicriteria scheduling on identical parallel machines in a nontraditional context: jobs belong to two disjoint sets, and each set has a different criterion to be minimized. The jobs are all available at time zero and have to be scheduled (non-preemptively) on m parallel machines. The goal is to generate the set of all non-dominated solutions, so the decision maker can evaluate the tradeoffs and choose the schedule to be implemented. We consider the case where, for one of the two sets, the criterion to be minimized is makespan while for the other the total completion time needs to be minimized. Given that the problem is NP-hard, we propose an iterative SPT-LPT-SPT heuristic and a bicriteria genetic algorithm for the problem. Both approaches are designed to exploit the problem structure and generate a set of non-dominated solutions. In the genetic algorithm we use a special encoding scheme and also a unique strategy - based on the properties of a non-dominated solution - to ensure that all parts of the non-dominated front are explored. The heuristic and the genetic algorithm are compared with a time-indexed integer programming formulation for small and large instances. Results indicate that the both the heuristic and the genetic algorithm provide high solution quality and are computationally efficient. The heuristics proposed also have the potential to be generalized for the problem of interfering job sets involving other bicriteria pairs.

Suggested Citation

  • 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.
    • Handle: RePEc:eee:ejores:v:199:y:2009:i:1:p:55-67
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377-2217(08)00968-5
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to

    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. C. T. Ng & T. C. E. Cheng & J. J. Yuan, 2006. "A note on the complexity of the problem of two-agent scheduling on a single machine," Journal of Combinatorial Optimization, Springer, vol. 12(4), pages 387-394, December.
    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. Loukil, T. & Teghem, J. & Tuyttens, D., 2005. "Solving multi-objective production scheduling problems using metaheuristics," European Journal of Operational Research, Elsevier, vol. 161(1), pages 42-61, February.
    5. SOUSA, Jorge P. & WOLSEY, Laurence A., 1992. "A time indexed formulation of non-preemptive single machine scheduling problems," LIDAM Reprints CORE 984, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    6. Alessandro Agnetis & Dario Pacciarelli & Andrea Pacifici, 2007. "Multi-agent single machine scheduling," Annals of Operations Research, Springer, vol. 150(1), pages 3-15, March.
    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. 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.
    2. Cheng, Shuenn-Ren, 2014. "Some new problems on two-agent scheduling to minimize the earliness costs," International Journal of Production Economics, Elsevier, vol. 156(C), pages 24-30.
    3. Kejun Zhao & Xiwen Lu, 2016. "Two approximation algorithms for two-agent scheduling on parallel machines to minimize makespan," Journal of Combinatorial Optimization, Springer, vol. 31(1), pages 260-278, January.
    4. Paz Perez-Gonzalez & Jose M. Framinan, 2018. "Single machine interfering jobs problem with flowtime objective," Journal of Intelligent Manufacturing, Springer, vol. 29(5), pages 953-972, June.
    5. Tifenn Rault & Faiza Sadi & Jean-Charles Billaut & Ameur Soukhal, 2024. "Scheduling two interfering job sets on identical parallel machines with makespan and total completion time minimization," Journal of Scheduling, Springer, vol. 27(5), pages 485-505, October.
    6. Donatas Elvikis & Vincent T’kindt, 2014. "Two-agent scheduling on uniform parallel machines with min-max criteria," Annals of Operations Research, Springer, vol. 213(1), pages 79-94, February.
    7. Yang-Kuei Lin & Tzu-Yueh Yin, 2022. "Generating bicriteria schedules for correlated parallel machines involving tardy jobs and weighted completion time," Annals of Operations Research, Springer, vol. 319(2), pages 1655-1688, December.
    8. Peihai Liu & Manzhan Gu & Xiwen Lu, 2024. "Two-agent scheduling in a two-machine open shop," Annals of Operations Research, Springer, vol. 333(1), pages 275-301, February.
    9. Lang, Fabian & Fink, Andreas & Brandt, Tobias, 2016. "Design of automated negotiation mechanisms for decentralized heterogeneous machine scheduling," European Journal of Operational Research, Elsevier, vol. 248(1), pages 192-203.
    10. Choi, Byung-Cheon & Park, Myoung-Ju, 2017. "Two-agent parallel machine scheduling with a restricted number of overlapped reserved tasks," European Journal of Operational Research, Elsevier, vol. 260(2), pages 514-519.

    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. 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.
    2. 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.
    3. 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.
    4. Nong, Q.Q. & Cheng, T.C.E. & Ng, C.T., 2011. "Two-agent scheduling to minimize the total cost," European Journal of Operational Research, Elsevier, vol. 215(1), pages 39-44, November.
    5. Ren-Xia Chen & Shi-Sheng Li, 2019. "Two-agent single-machine scheduling with cumulative deterioration," 4OR, Springer, vol. 17(2), pages 201-219, June.
    6. Joseph Y.-T. Leung & Michael Pinedo & Guohua Wan, 2010. "Competitive Two-Agent Scheduling and Its Applications," Operations Research, INFORMS, vol. 58(2), pages 458-469, April.
    7. Zhang Xingong & Wang Yong, 2017. "Two-agent scheduling problems on a single-machine to minimize the total weighted late work," Journal of Combinatorial Optimization, Springer, vol. 33(3), pages 945-955, April.
    8. 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.
    9. Yuan Zhang & Jinjiang Yuan, 2019. "A note on a two-agent scheduling problem related to the total weighted late work," Journal of Combinatorial Optimization, Springer, vol. 37(3), pages 989-999, April.
    10. Wenchang Luo & Lin Chen & Guochuan Zhang, 2012. "Approximation schemes for two-machine flow shop scheduling with two agents," Journal of Combinatorial Optimization, Springer, vol. 24(3), pages 229-239, October.
    11. Shi-Sheng Li & Jin-Jiang Yuan, 2020. "Single-machine scheduling with multi-agents to minimize total weighted late work," Journal of Scheduling, Springer, vol. 23(4), pages 497-512, August.
    12. Fan, B.Q. & Cheng, T.C.E., 2016. "Two-agent scheduling in a flowshop," European Journal of Operational Research, Elsevier, vol. 252(2), pages 376-384.
    13. Yunqiang Yin & T. C. E. Cheng & Du-Juan Wang & Chin-Chia Wu, 2017. "Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs," Journal of Scheduling, Springer, vol. 20(4), pages 313-335, August.
    14. 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.
    15. Kuo-Ching Ying & Pourya Pourhejazy & Chuan-En Sung, 2024. "Two-agent proportionate flowshop scheduling with deadlines: polynomial-time optimization algorithms," Annals of Operations Research, Springer, vol. 343(1), pages 543-558, December.
    16. Cheng He & Chunqi Xu & Hao Lin, 2020. "Serial-batching scheduling with two agents to minimize makespan and maximum cost," Journal of Scheduling, Springer, vol. 23(5), pages 609-617, October.
    17. Byung-Cheon Choi & Myoung-Ju Park, 2016. "An Ordered Flow Shop with Two Agents," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 33(05), pages 1-24, October.
    18. Shesh Narayan Sahu & Yuvraj Gajpal & Swapan Debbarma, 2018. "Two-agent-based single-machine scheduling with switchover time to minimize total weighted completion time and makespan objectives," Annals of Operations Research, Springer, vol. 269(1), pages 623-640, October.
    19. Ruyan He & Jinjiang Yuan, 2020. "Two-Agent Preemptive Pareto-Scheduling to Minimize Late Work and Other Criteria," Mathematics, MDPI, vol. 8(9), pages 1-18, September.
    20. 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.

    More about this item

    Keywords

    ;

    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:eee:ejores:v:199:y:2009:i:1:p:55-67. 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.