Single machine minsum and minmax common due date assignment and scheduling problems involving general position-dependent workloads

Department of Economics and Business Administration, Ariel University, Ariel 40700, Israel

^* Corresponding author: baruchm@ariel.ac.il

Received: 11 August 2023
Accepted: 15 December 2024

Abstract

This study addresses the well-known scheduling and assignment problem with a common due date. Four cost components are assumed, i.e., earliness, tardiness, the cost of delaying the due date, and extended total completion time. The minsum and the minmax versions of the fundamental problem are solved. For each of the major versions of the classic scheduling theory assuming jobs with position-independent processing times, a detailed analysis is provided, and, consequently, the properties of an optimal solution and a closed-form solution. These elementary results lay the foundation for two extensions. The first extension is for jobs with variable processing times and focuses on general position-dependent processing times. The second extension considers the recently introduced convex resource allocation method with general position-dependent workloads and continuous non-renewable resource. All studied problems are shown to be solved in polynomial time, such that the computational complexity of the minsum and minmax position-independent processing time variants are O(n log n) and O(n), respectively, and the computational complexity of the variants involving variable processing times is O(n³).