Due date assignment and two-agent scheduling under multitasking environment

Yongjian Yang, Guangqiang Yin, Chunyu Wang and Yunqiang Yin ()
Additional contact information
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

Journal of Combinatorial Optimization, 2022, vol. 44, issue 4, No 4, 2207-2223

Abstract: 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.

Keywords: Multitasking scheduling; Two agents; DIF due date assignment; Dynamic programming (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00600-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:44:y:2022:i:4:d:10.1007_s10878-020-00600-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00600-5

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().