Title
Scheduling with assignable due dates, two competing agents and late work related criteria
Authors
[ 1 ] Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | [ P ] employee
Scientific discipline (Law 2.0)
Year of publication
2025
Published in
Article type
scientific article
Publication language
english
Keywords
EN
- Scheduling
- Single machine
- Two-agent
- Assignable due dates
- Late work
Abstract
EN This paper investigates several scheduling problems on a single machine that exhibit three key features: (i) assignable due dates are considered, meaning that a predefined set of due dates is provided, and these due dates can be assigned to the jobs independently and arbitrarily; (ii) two competing agents are involved, with jobs divided into two disjoint sets, each owned by one agent; and (iii) each agent’s objective is to minimize a specific late work-related criterion. Specifically, the goal is to determine a due date assignment and a feasible schedule that minimizes the weighted sum of the selected scheduling criteria for both agents. For the first time, we integrate two-agent scheduling, assignable due dates, and late work-related criteria. We develop pseudo-polynomial-time dynamic programming algorithms to address problems where one agent’s criterion is the total late work, while the other agent’s criterion is either the total late work, total tardiness, or weighted number of tardy jobs. Moreover, we propose polynomial-time algorithms to tackle various special cases of these related problems.
Date of online publication
28.05.2025
Pages (from - to)
107144-1 - 107144-16
Comments
Article Number: 107144
Ministry points / journal
140
Impact Factor
4,1 [List 2023]
System created by Poznań University of Technology
and Poznan Supercomputing and Networking Center
Log in through eKonto to add to SIS