Single-machine multitasking scheduling with job efficiency promotion

Min Ji, Yingchun Zhang, Yuan Zhang, T. C.E. Cheng, Yiwei Jiang

Research output: Journal article publicationJournal articleAcademic researchpeer-review


Motivated by behavioural and psychological phenomena that occur in human operators, we study single-machine multitasking scheduling with job efficiency promotion. In traditional multitasking scheduling, the primary task is assumed to be interrupted by every waiting task. In this paper we take into account job efficiency promotion that helps reduce the actual interruption time. We propose two functions to model job efficiency promotion based on the job positions in a given schedule. The objective is to minimize the makespan, total completion time, and total absolute difference in completion times. We show that the problem is polynomially solvable for each objective. We also provide efficient solutions for some special cases.

Original languageEnglish
JournalJournal of Combinatorial Optimization
Publication statusAccepted/In press - 2022


  • Efficiency promotion
  • Human multitasking
  • Multitasking scheduling
  • Optimization
  • Scheduling
  • Single machine

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this