IDEAS home Printed from https://ideas.repec.org/a/spr/joinma/v29y2018i5d10.1007_s10845-015-1141-6.html
   My bibliography  Save this article

Single machine interfering jobs problem with flowtime objective

Author

Listed:
  • Paz Perez-Gonzalez

    (University of Seville)

  • Jose M. Framinan

    (University of Seville)

Abstract

Interfering jobs problems (or multi agents scheduling problems) are an emergent topic in the scheduling literature. In these decision problems, two or more sets of jobs have to be scheduled, each one with its own criteria. More specifically, we focus on a problem in which jobs belonging to two sets have to be scheduled in a single machine in order to minimize the total flowtime of the jobs in one set, while the total flowtime of the jobs in the other set should not exceed a given constant $$\epsilon $$ ϵ . This problem is known to be weakly NP-hard, and, in the literature, a dynamic programming (DP) algorithm has been proposed to find optimal solutions. In this paper, we first analyse the distribution of solutions of the problem in order to establish its empirical hardness. Next, a novel encoding scheme and a set of properties associated to the neighbourhood of this scheme are presented. These properties are used to develop both exact and approximate methods, i.e. a branch and bound (B&B) method, several constructive heuristics, and different versions of a genetic algorithm (GA). The computational experience carried out shows that the proposed B&B is more efficient than the existing DP algorithm. The results also show the advantages of the proposed encoding scheme, as the approximate methods yield close-to-optimum solutions for big-sized instances where exact methods are not feasible.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:joinma:v:29:y:2018:i:5:d:10.1007_s10845-015-1141-6
    DOI: 10.1007/s10845-015-1141-6
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10845-015-1141-6
    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/s10845-015-1141-6?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. Tseng, Lin-Yu & Lin, Ya-Tai, 2010. "A genetic local search algorithm for minimizing total flowtime in the permutation flowshop scheduling problem," International Journal of Production Economics, Elsevier, vol. 127(1), pages 121-128, September.
    2. Taillard, E., 1990. "Some efficient heuristic methods for the flow shop sequencing problem," European Journal of Operational Research, Elsevier, vol. 47(1), pages 65-74, July.
    3. Yuan, Jinjiang & Mu, Yundong, 2007. "Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption," European Journal of Operational Research, Elsevier, vol. 182(2), pages 936-944, October.
    4. Jinjiang Yuan & Yundong Mu & Lingfa Lu & Wenhua Li, 2007. "Rescheduling With Release Dates To Minimize Total Sequence Disruption Under A Limit On The Makespan," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 24(06), pages 789-796.
    5. Ali Tamer Unal & Reha Uzsoy & Ali Kiran, 1997. "Rescheduling on a single machine with part-type dependent setup times and deadlines," Annals of Operations Research, Springer, vol. 70(0), pages 93-113, April.
    6. 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.
    7. Ruiz, Ruben & Maroto, Concepcion, 2006. "A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility," European Journal of Operational Research, Elsevier, vol. 169(3), pages 781-800, March.
    8. Nicholas G. Hall & Chris N. Potts, 2004. "Rescheduling for New Orders," Operations Research, INFORMS, vol. 52(3), pages 440-453, June.
    9. 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.
    10. Wan, Guohua & Vakati, Sudheer R. & Leung, Joseph Y.-T. & Pinedo, Michael, 2010. "Scheduling two agents with controllable processing times," European Journal of Operational Research, Elsevier, vol. 205(3), pages 528-539, September.
    11. Purushothaman Damodaran & Neal S. Hirani & Mario C. Velez-Gallego, 2009. "Scheduling identical parallel batch processing machines to minimise makespan using genetic algorithms," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 3(2), pages 187-206.
    12. Ruiz, Ruben & Maroto, Concepcion & Alcaraz, Javier, 2005. "Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics," European Journal of Operational Research, Elsevier, vol. 165(1), pages 34-54, August.
    13. 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.
    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. 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. Qiulan Zhao & Lingfa Lu & Jinjiang Yuan, 2016. "Rescheduling with new orders and general maximum allowable time disruptions," 4OR, Springer, vol. 14(3), pages 261-280, September.
    3. Liu, Zhixin & Lu, Liang & Qi, Xiangtong, 2018. "Cost allocation in rescheduling with machine unavailable period," European Journal of Operational Research, Elsevier, vol. 266(1), pages 16-28.
    4. Byung-Cheon Choi & Myoung-Ju Park, 2020. "Scheduling two projects with controllable processing times in a single-machine environment," Journal of Scheduling, Springer, vol. 23(5), pages 619-628, October.
    5. 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.
    6. Du-Juan Wang & Yunqiang Yin & Shuenn-Ren Cheng & T.C.E. Cheng & Chin-Chia Wu, 2016. "Due date assignment and scheduling on a single machine with two competing agents," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 1152-1169, February.
    7. Hoogeveen, H. & Lenté, C. & T’kindt, V., 2012. "Rescheduling for new orders on a single machine with setup times," European Journal of Operational Research, Elsevier, vol. 223(1), pages 40-46.
    8. Qiulan Zhao & Jinjiang Yuan, 2017. "Rescheduling to Minimize the Maximum Lateness Under the Sequence Disruptions of Original Jobs," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(05), pages 1-12, October.
    9. Yunqiang Yin & Yongjian Yang & Dujuan Wang & T.C.E. Cheng & Chin‐Chia Wu, 2018. "Integrated production, inventory, and batch delivery scheduling with due date assignment and two competing agents," Naval Research Logistics (NRL), John Wiley & Sons, vol. 65(5), pages 393-409, August.
    10. Ruiz, Ruben & Stutzle, Thomas, 2007. "A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem," European Journal of Operational Research, Elsevier, vol. 177(3), pages 2033-2049, March.
    11. 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.
    12. Yunqiang Yin & Du‐Juan Wang & Chin‐Chia Wu & T.C.E. Cheng, 2016. "CON/SLK due date assignment and scheduling on a single machine with two agents," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(5), pages 416-429, August.
    13. Byung-Gyoo Kim & Byung-Cheon Choi & Myoung-Ju Park, 2017. "Two-Machine and Two-Agent Flow Shop with Special Processing Times Structures," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 34(04), pages 1-17, August.
    14. 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.
    15. Yunqiang Yin & Youhua Chen & Kaida Qin & Dujuan Wang, 2019. "Two-agent scheduling on unrelated parallel machines with total completion time and weighted number of tardy jobs criteria," Journal of Scheduling, Springer, vol. 22(3), pages 315-333, June.
    16. Zhang, Xingong, 2021. "Two competitive agents to minimize the weighted total late work and the total completion time," Applied Mathematics and Computation, Elsevier, vol. 406(C).
    17. Yongjian Yang & Guangqiang Yin & Chunyu Wang & Yunqiang Yin, 0. "Due date assignment and two-agent scheduling under multitasking environment," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-17.
    18. Yongjian Yang & Guangqiang Yin & Chunyu Wang & Yunqiang Yin, 2022. "Due date assignment and two-agent scheduling under multitasking environment," Journal of Combinatorial Optimization, Springer, vol. 44(4), pages 2207-2223, November.
    19. Yin, Yunqiang & Cheng, T.C.E. & Wang, Du-Juan, 2016. "Rescheduling on identical parallel machines with machine disruptions to minimize total completion time," European Journal of Operational Research, Elsevier, vol. 252(3), pages 737-749.
    20. 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.

    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:joinma:v:29:y:2018:i:5:d:10.1007_s10845-015-1141-6. 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.