{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T06:12:06Z","timestamp":1770963126936,"version":"3.50.1"},"reference-count":53,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T00:00:00Z","timestamp":1770595200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>In the presence of multitasking, a worker has to concurrently handle interruptions from the waiting jobs and routine jobs while processing a primary job. For over a decade, various studies in this research direction have been conducted aiming to figure out how jobs are scheduled so as to reduce the effect due to multitasking. In this paper, two late-job problems in line with the classical late-job problems are tackled. In contrast to the classical setting in which all jobs must be completed, we suggest the idea of outsourcing. Some jobs are outsourced. Thus, the worker only processes the on-time jobs and handles the interruptions from the waiting jobs. Each outsourced job is assigned to a single freelancer to ensure that all jobs are completed on-time. The overhead is the charges to the freelancers, i.e., the total outsourcing cost. If the service charges of all the jobs are the same, the late-job problem is called the total number of outsourcing jobs (TNOJ) problem, which is in-line with the classical total number of late-job problems. If the service charges are different, the late-job problem is called the total weighted number of outsourcing jobs (TWNOJ) problem, which is in-line with the classical total weighted number of late-job problems. For general settings, it is proved that the TNOJ problem is NP-hard and the TWNOJ problem is strongly NP-hard. If the interruption of a waiting job is proportional to its remaining processing time, the TNOJ problem can be solved in O(nlog(n)P)-time and the TWNOJ problem can be solved in O(nP2)-time, where n is the number of jobs and P denotes the sum of their processing times.<\/jats:p>","DOI":"10.3390\/a19020141","type":"journal-article","created":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T18:02:01Z","timestamp":1770660121000},"page":"141","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Scheduling with Multitasking and Outsourcing"],"prefix":"10.3390","volume":"19","author":[{"given":"John","family":"Sum","sequence":"first","affiliation":[{"name":"Institute of Technology Management, National Chung Hsing University, Taichung 402, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kevin I. J.","family":"Ho","sequence":"additional","affiliation":[{"name":"Center for Electronic Commerce & Knowledge Economics Research, National Chung Hsing University, Taichung 402, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2026,2,9]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1016\/j.ergon.2008.05.001","article-title":"Taxonomy for integrating scheduling theory and human factors: Review and research opportunities","volume":"39","author":"Lodree","year":"2009","journal-title":"Int. J. Ind. Ergon."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/0020-0190(93)90175-9","article-title":"Complexity of scheduling tasks with time-dependent execution times","volume":"48","author":"Ho","year":"1993","journal-title":"Inf. Process. Lett."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0377-2217(98)00246-X","article-title":"Single-machine scheduling with learning considerations","volume":"115","author":"Biskup","year":"1999","journal-title":"Eur. J. Oper. Res."},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1016\/j.ejor.2007.05.040","article-title":"A state-of-the-art review on scheduling with learning effects","volume":"188","author":"Biskup","year":"2008","journal-title":"Eur. J. Oper. Res."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"837","DOI":"10.1016\/j.apm.2009.07.002","article-title":"Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan","volume":"34","author":"Zhao","year":"2010","journal-title":"Appl. Math. Model."},{"key":"ref_6","first-page":"105","article-title":"The myth of multitasking","volume":"20","author":"Rosen","year":"2008","journal-title":"New Atlantis"},{"key":"ref_7","first-page":"127","article-title":"The Myth of Multitasking","volume":"2","author":"BAUM","year":"2024","journal-title":"Healthc. Adm. Leadersh. Manag. J."},{"key":"ref_8","unstructured":"Lee, F.J., and Taatgen, N.A. (2002). Multitasking as skill acquisition. Proceedings of the Annual Meeting of the Cognitive Science Society, Boston, MA, USA, 1 July\u20133 August 2003, Routledge. Available online: https:\/\/escholarship.org\/uc\/item\/02b1h7dg."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1518\/hfes.45.1.61.27224","article-title":"Production compilation: A simple mechanism to model complex skill acquisition","volume":"45","author":"Taatgen","year":"2003","journal-title":"Hum. Factors"},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"11778","DOI":"10.1073\/pnas.0602659103","article-title":"Modulation of competing memory systems by distraction","volume":"103","author":"Foerde","year":"2006","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_11","first-page":"55","article-title":"Overloaded circuits","volume":"83","author":"Hallowell","year":"2005","journal-title":"Harv. Bus. Rev."},{"key":"ref_12","unstructured":"Woolston, C. (2026, January 14). Multitasking and Stress. Available online: https:\/\/simhcottumwa.org\/multitasking-and-stress\/."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Becker, L., Kaltenegger, H.C., Nowak, D., Weigl, M., and Rohleder, N. (2022). Physiological stress in response to multitasking and work interruptions: Study protocol. PLoS ONE, 17.","DOI":"10.1371\/journal.pone.0263785"},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/isre.1110.0408","article-title":"Information, technology and information worker productivity: Task level evidence","volume":"23","author":"Aral","year":"2007","journal-title":"Inf. Syst. Res."},{"key":"ref_15","doi-asserted-by":"crossref","unstructured":"Coviello, D., Ichino, A., and Persico, N. (2010). Don\u2019t Spread Yourself Too Thin: The Impact of Task Juggling on Workers\u2019 Speed of Job Completion, National Bureau of Economic Research. Technical Report.","DOI":"10.3386\/w16502"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"849","DOI":"10.1287\/isre.1110.0408","article-title":"Information, technology, and information worker productivity","volume":"23","author":"Aral","year":"2012","journal-title":"Inf. Syst. Res."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"609","DOI":"10.1257\/aer.104.2.609","article-title":"Time allocation and task juggling","volume":"104","author":"Coviello","year":"2014","journal-title":"Am. Econ. Rev."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"763","DOI":"10.1037\/0096-1523.27.4.763","article-title":"Executive control of cognitive processes in task switching","volume":"27","author":"Rubinstein","year":"2001","journal-title":"J. Exp. Psychol. Hum. Percept. Perform."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"7212","DOI":"10.1073\/pnas.1015297108","article-title":"Deficit in switching between functional brain networks underlies the impact of multitasking on working memory in older adults","volume":"108","author":"Clapp","year":"2011","journal-title":"Proc. Natl. Acad. Sci. USA"},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Loukopoulos, L.D., Dismukes, R.K., and Barshi, I. (2016). The Multitasking Myth: Handling Complexity in Real-World Operations, Routledge.","DOI":"10.4324\/9781315555416"},{"key":"ref_21","unstructured":"Hall, N.G., Leung, J.Y.T., and Li, C.L. (2013). Scheduling with Multitasking, unpublished manuscript."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1248","DOI":"10.1111\/poms.12331","article-title":"The effects of multitasking on operations scheduling","volume":"24","author":"Hall","year":"2015","journal-title":"Prod. Oper. Manag."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Sum, J., and Ho, K. (2015, January 9\u201312). Analysis on the effect of multitasking. Proceedings of the 2015 IEEE International Conference on Systems, Man, and Cybernetics, Kowloon Tong, Hong Kong.","DOI":"10.1109\/SMC.2015.48"},{"key":"ref_24","unstructured":"Sum, J., and Ho, K.I.J. (2015, January 30). Operations scheduling in the presence of multitasking and symmetric switching cost. Proceedings of the International Conference on Management Science and Decision Making, Taipei, Taiwan. Available online: https:\/\/john.digi-pack.io\/papers\/2015-ICMSDM-Operations-Scheduling.pdf."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Ho, K.I.J., and Sum, J. (2017, January 5\u20138). Scheduling jobs with multitasking and asymmetric switching costs. Proceedings of the 2017 IEEE International Conference on Systems, Man, and Cybernetics (SMC), Banff, AB, Canada.","DOI":"10.1109\/SMC.2017.8123072"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"6052","DOI":"10.1080\/00207543.2017.1321804","article-title":"Algorithms for the joint multitasking scheduling and common due date assignment problem","volume":"55","author":"Liu","year":"2017","journal-title":"Int. J. Prod. Res."},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1080\/00207543.2016.1208852","article-title":"Multitasking scheduling problems with a rate-modifying activity","volume":"55","author":"Zhu","year":"2017","journal-title":"Int. J. Prod. Res."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"4750791","DOI":"10.1155\/2017\/4750791","article-title":"Multitasking scheduling problems with deterioration effect","volume":"2017","author":"Zhu","year":"2017","journal-title":"Math. Probl. Eng."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"1956","DOI":"10.1111\/itor.12393","article-title":"Multitasking scheduling with multiple rate-modifying activities","volume":"26","author":"Zhu","year":"2019","journal-title":"Int. Trans. Oper. Res."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1016\/j.dam.2016.03.018","article-title":"Multitasking via alternate and shared processing: Algorithms and complexity","volume":"208","author":"Hall","year":"2016","journal-title":"Discret. Appl. Math."},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"54","DOI":"10.1080\/24725854.2017.1380334","article-title":"Task scheduling with progress control","volume":"50","author":"Li","year":"2018","journal-title":"IISE Trans."},{"key":"ref_32","doi-asserted-by":"crossref","first-page":"1667","DOI":"10.1080\/00207543.2018.1497312","article-title":"Multitasking parallel-machine scheduling with machine-dependent slack due-window assignment","volume":"57","author":"Ji","year":"2019","journal-title":"Int. J. Prod. Res."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"502","DOI":"10.1002\/nav.21863","article-title":"An exact branch-and-price algorithm for multitasking scheduling on unrelated parallel machines","volume":"66","author":"Xiong","year":"2019","journal-title":"Nav. Res. Logist."},{"key":"ref_34","doi-asserted-by":"crossref","first-page":"3633","DOI":"10.1080\/00207543.2020.1748908","article-title":"Multi-agent scheduling problems under multitasking","volume":"59","author":"Wang","year":"2021","journal-title":"Int. J. Prod. Res."},{"key":"ref_35","doi-asserted-by":"crossref","unstructured":"Xin, X., Zhou, S., and Gao, J. (2025). An exact approach for multitasking scheduling with two competitive agents on identical parallel machines. Appl. Sci., 15.","DOI":"10.3390\/app152212111"},{"key":"ref_36","doi-asserted-by":"crossref","first-page":"1940","DOI":"10.1080\/0305215X.2019.1678609","article-title":"Multitasking scheduling problems with two competitive agents","volume":"52","author":"Li","year":"2020","journal-title":"Eng. Optim."},{"key":"ref_37","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s40747-021-00355-4","article-title":"A two-agent one-machine multitasking scheduling problem solving by exact and metaheuristics","volume":"8","author":"Wu","year":"2022","journal-title":"Complex Intell. Syst."},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"2207","DOI":"10.1007\/s10878-020-00600-5","article-title":"Due date assignment and two-agent scheduling under multitasking environment","volume":"44","author":"Yang","year":"2022","journal-title":"J. Comb. Optim."},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"595","DOI":"10.1002\/nav.22167","article-title":"Multitasking scheduling with shared processing","volume":"71","author":"Fu","year":"2024","journal-title":"Nav. Res. Logist. (NRL)"},{"key":"ref_40","doi-asserted-by":"crossref","first-page":"691","DOI":"10.1016\/0014-2921(94)90104-X","article-title":"Job design, delegation and cooperation: A principal-agent analysis","volume":"38","author":"Itoh","year":"1994","journal-title":"Eur. Econ. Rev."},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"467","DOI":"10.1111\/j.1756-2171.2007.tb00078.x","article-title":"Teams versus individual accountability: Solving multitask problems through job design","volume":"38","author":"Corts","year":"2007","journal-title":"RAND J. Econ."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"243","DOI":"10.1007\/BF00309260","article-title":"What makes interruptions disruptive? A study of length, similarity, and complexity","volume":"50","author":"Gillie","year":"1989","journal-title":"Psychol. Res."},{"key":"ref_43","doi-asserted-by":"crossref","first-page":"134","DOI":"10.1016\/S1364-6613(03)00028-7","article-title":"Task switching","volume":"7","author":"Monsell","year":"2003","journal-title":"Trends Cogn. Sci."},{"key":"ref_44","doi-asserted-by":"crossref","first-page":"417","DOI":"10.1007\/s10951-008-0090-8","article-title":"A survey of dynamic scheduling in manufacturing systems","volume":"12","author":"Ouelhadj","year":"2009","journal-title":"J. Sched."},{"key":"ref_45","doi-asserted-by":"crossref","unstructured":"Vanhoucke, M. (2012). Project Management with Dynamic Scheduling: Baseline Scheduling, Risk Analysis and Project Control, Springer. [2nd ed.].","DOI":"10.1007\/978-3-642-25175-7"},{"key":"ref_46","doi-asserted-by":"crossref","unstructured":"Ngwu, C., Liu, Y., and Wu, R. (2025). Reinforcement learning in dynamic job shop scheduling: A comprehensive review of AI-driven approaches in modern manufacturing. J. Intell. Manuf., 1\u201316.","DOI":"10.1007\/s10845-025-02585-6"},{"key":"ref_47","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/s10462-025-11208-8","article-title":"AI-Driven job scheduling in cloud computing: A comprehensive review","volume":"58","author":"Sanjalawe","year":"2025","journal-title":"Artif. Intell. Rev."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"606","DOI":"10.1016\/S0377-2217(00)00281-2","article-title":"Sensitivity analysis of scheduling algorithms","volume":"134","author":"Penz","year":"2001","journal-title":"Eur. J. Oper. Res."},{"key":"ref_49","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1023\/B:JOSH.0000013055.31639.f6","article-title":"Sensitivity analysis for scheduling problems","volume":"7","author":"Hall","year":"2004","journal-title":"J. Sched."},{"key":"ref_50","unstructured":"Garey, M.R., and Johnson, D.S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness, WH Freeman and Company."},{"key":"ref_51","doi-asserted-by":"crossref","unstructured":"Pinedo, M. (1992). Scheduling: Theory, Algorithms, and Systems, Prentice-Hall. [1st ed.].","DOI":"10.1007\/978-3-642-46773-8_5"},{"key":"ref_52","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1287\/mnsc.15.1.102","article-title":"An n job, one machine sequencing algorithm for minimizing the number of late jobs","volume":"15","author":"Moore","year":"1968","journal-title":"Manag. Sci."},{"key":"ref_53","unstructured":"Pinedo, M. (2015). Scheduling: Theory, Algorithms, and Systems, Springer. [3rd ed.]."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/2\/141\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T05:20:51Z","timestamp":1770960051000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/19\/2\/141"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,9]]},"references-count":53,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2026,2]]}},"alternative-id":["a19020141"],"URL":"https:\/\/doi.org\/10.3390\/a19020141","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,9]]}}}