IDEAS home Printed from https://ideas.repec.org/a/spr/jcomop/v44y2022i4d10.1007_s10878-020-00600-5.html
   My bibliography  Save this article

Due date assignment and two-agent scheduling under multitasking environment

Author

Listed:
  • Yongjian Yang

    (University of Electronic Science and Technology of China)

  • Guangqiang Yin

    (University of Electronic Science and Technology of China)

  • Chunyu Wang

    (University of Electronic Science and Technology of China)

  • Yunqiang Yin

    (University of Electronic Science and Technology of China)

Abstract

This paper addresses a two-agent scheduling problem with due date assignment under multitasking environment, in which the due dates of the jobs from the first agent are decision variables to be determined using the unrestricted (usually referred to as DIF) due date assignment method. Each agent requests the processing of its own set of jobs on a machine and wishes to minimize a certain scheduling criterion related to the completion times of its jobs only. Under multitasking, when a job (primary job) is processed, it is inevitably interrupted by other jobs (waiting jobs) that are available but unfinished, and the amount of time that each waiting job interrupting the primary job is a linear function of the remaining processing time of the waiting job. The overall objective is to determine the optimal primary job sequence along with the due dates of the jobs from the first agent as to minimize the weighted sum of the due date assignment cost and weighted number of late jobs from the first agent, while maintaining the total completion time of the jobs from the second agent not exceeding a given threshold. We show that the problem is $$\mathcal {NP}$$ NP -hard, devise a pseudo-polynomial time dynamic programming algorithm, establishing that it is $$\mathcal {NP}$$ NP -hard in the ordinary sense, and demonstrate that it admits a fully polynomial-time approximation scheme.

Suggested Citation

  • 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.
  • Handle: RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-020-00600-5
    DOI: 10.1007/s10878-020-00600-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10878-020-00600-5
    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/s10878-020-00600-5?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. Sridhar Seshadri & Zur Shapira, 2001. "Managerial Allocation of Time and Effort: The Effects of Interruptions," Management Science, INFORMS, vol. 47(5), pages 647-662, May.
    2. 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.
    3. Enrique Gerstl & Gur Mosheiov, 2014. "Single machine just‐in‐time scheduling problems with two competing agents," Naval Research Logistics (NRL), John Wiley & Sons, vol. 61(1), pages 1-16, February.
    4. Ming Liu & Shijin Wang & Feifeng Zheng & Chengbin Chu, 2017. "Algorithms for the joint multitasking scheduling and common due date assignment problem," International Journal of Production Research, Taylor & Francis Journals, vol. 55(20), pages 6052-6066, October.
    5. Nicholas G. Hall & Joseph Y.-T. Leung & Chung-Lun Li, 2015. "The Effects of Multitasking on Operations Scheduling," Production and Operations Management, Production and Operations Management Society, vol. 24(8), pages 1248-1265, August.
    6. 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.
    7. 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.
    8. Decio Coviello & Andrea Ichino & Nicola Persico, 2014. "Time Allocation and Task Juggling," American Economic Review, American Economic Association, vol. 104(2), pages 609-623, February.
    9. Amanda Spink & H. Cenk Ozmutlu & Seda Ozmutlu, 2002. "Multitasking information seeking and searching processes," Journal of the American Society for Information Science and Technology, Association for Information Science & Technology, vol. 53(8), pages 639-652.
    10. Xiaoyun Xiong & Peng Zhou & Yunqiang Yin & T. C. E. Cheng & Dengfeng Li, 2019. "An exact branch‐and‐price algorithm for multitasking scheduling on unrelated parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(6), pages 502-516, September.
    11. Gerhard J. Woeginger, 2000. "When Does a Dynamic Programming Formulation Guarantee the Existence of a Fully Polynomial Time Approximation Scheme (FPTAS)?," INFORMS Journal on Computing, INFORMS, vol. 12(1), pages 57-74, February.
    12. Min Ji & Wenya Zhang & Lijuan Liao & T. C. E. Cheng & Yuanyuan Tan, 2019. "Multitasking parallel-machine scheduling with machine-dependent slack due-window assignment," International Journal of Production Research, Taylor & Francis Journals, vol. 57(6), pages 1667-1684, March.
    13. Wang, Du-Juan & Yin, Yunqiang & Xu, Jianyou & Wu, Wen-Hsiang & Cheng, Shuenn-Ren & Wu, Chin-Chia, 2015. "Some due date determination scheduling problems with two agents on a single machine," International Journal of Production Economics, Elsevier, vol. 168(C), pages 81-90.
    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. Hongyu He & Yanzhi Zhao & Xiaojun Ma & Zheng-Guo Lv & Ji-Bo Wang, 2023. "Branch-and-Bound and Heuristic Algorithms for Group Scheduling with Due-Date Assignment and Resource Allocation," Mathematics, MDPI, vol. 11(23), pages 1-14, November.
    2. Lei Pan & Xinyu Sun & Ji-Bo Wang & Li-Han Zhang & Dan-Yang Lv, 2023. "Due date assignment single-machine scheduling with delivery times, position-dependent weights and deteriorating jobs," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-16, May.
    3. Yujia Huo & Cuixia Miao & Fanyu Kong & Yuzhong Zhang, 2023. "Multitasking scheduling with alternate periods," Journal of Combinatorial Optimization, Springer, vol. 45(3), pages 1-13, April.

    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. 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.
    2. Min Ji & Yingchun Zhang & Yuan Zhang & T. C. E. Cheng & Yiwei Jiang, 2022. "Single-machine multitasking scheduling with job efficiency promotion," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 446-479, August.
    3. Wang, Du-Juan & Yin, Yunqiang & Xu, Jianyou & Wu, Wen-Hsiang & Cheng, Shuenn-Ren & Wu, Chin-Chia, 2015. "Some due date determination scheduling problems with two agents on a single machine," International Journal of Production Economics, Elsevier, vol. 168(C), pages 81-90.
    4. 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.
    5. 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.
    6. 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.
    7. Xiaoyun Xiong & Peng Zhou & Yunqiang Yin & T. C. E. Cheng & Dengfeng Li, 2019. "An exact branch‐and‐price algorithm for multitasking scheduling on unrelated parallel machines," Naval Research Logistics (NRL), John Wiley & Sons, vol. 66(6), pages 502-516, September.
    8. 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.
    9. 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.
    10. Dujuan Wang & Yugang Yu & Huaxin Qiu & Yunqiang Yin & T. C. E. Cheng, 2020. "Two‐agent scheduling with linear resource‐dependent processing times," Naval Research Logistics (NRL), John Wiley & Sons, vol. 67(7), pages 573-591, October.
    11. 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.
    12. 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.
    13. Yunqiang Yin & Doudou Li & Dujuan Wang & T. C. E. Cheng, 2021. "Single-machine serial-batch delivery scheduling with two competing agents and due date assignment," Annals of Operations Research, Springer, vol. 298(1), pages 497-523, March.
    14. 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.
    15. 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.
    16. 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.
    17. 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).
    18. 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.
    19. Liang Tang & Zhihong Jin & Xuwei Qin & Ke Jing, 2019. "Supply chain scheduling in a collaborative manufacturing mode: model construction and algorithm design," Annals of Operations Research, Springer, vol. 275(2), pages 685-714, April.
    20. Vahid Nasrollahi & Ghasem Moslehi & Mohammad Reisi-Nafchi, 2022. "Minimizing the weighted sum of maximum earliness and maximum tardiness in a single-agent and two-agent form of a two-machine flow shop scheduling problem," Operational Research, Springer, vol. 22(2), pages 1403-1442, April.

    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:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-020-00600-5. 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.