Approximation algorithms for makespan minimization: restricted assignments, interval uncertainties, and price of connectivity

Sengupta, Raunak

Permalink

https://hdl.handle.net/2142/132519 Copy

Description

Title

Approximation algorithms for makespan minimization: restricted assignments, interval uncertainties, and price of connectivity

Author(s)

Sengupta, Raunak

Issue Date

2025-11-24

Director of Research (if dissertation) or Advisor (if thesis)

• Nagi, Rakesh
• Sreenivas, Ramavarapu S.

Doctoral Committee Chair(s)

• Nagi, Rakesh
• Sreenivas, Ramavarapu S.

Committee Member(s)

• Mehta, Ruta
• Etesami, Rasoul

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois Urbana-Champaign

Degree Name

Ph.D.

Degree Level

Dissertation

Keyword(s)

• Approximation Algorithms
• Scheduling

Abstract

The makespan minimization problem involves assigning a set of n jobs to a set of m agents or machines, where each job has an associated processing time dependent on the agent performing it. The goal is to minimize the maximum total completion time (makespan) across all agents. This canonical scheduling problem appears naturally in a wide array of applications. Given its broad applicability and theoretical richness, the makespan minimization problem has garnered extensive attention from the operations research and theoretical computer science communities. Despite numerous advancements, significant theoretical gaps and practical open questions persist, even for specialized variants of the problem. In this thesis, we study several variants of the makespan minimization problem, addressing key theoretical challenges and practically relevant constraints. Through carefully designed algorithmic approaches, we improve upon existing approximation guarantees, derive new bounds for previously unexplored variants, and identify critical structural properties that deepen the understanding of the problem. In the first part of the thesis, we investigate the (1,ϵ)-Restricted Assignment Makespan Minimization problem, a notable variant of the makespan minimization problem whose hardness has remained unresolved. We present a polynomial-time 1.5 approximation algorithm for the simpler variant where large jobs have no restrictions, followed by a non-polynomial local search algorithm (polynomial time if the number of machines are fixed) achieving a 5/3-approximation bound for the general case, improving upon the previously best-known bound of 5/3 +ϵ (0 < ϵ < 1 is the processing time of the ‘small’ jobs). The approach presented in this thesis diverges significantly from prevalent approaches by not using the Configuration Linear Program (LP) for its analysis. We transfer small jobs along “Light Alternating Paths” and large jobs along “Heavy Alternating Paths” in a structured manner which leads to the above mentioned bounds and an interesting topological ordering of the agents. In the second part of the thesis, we consider the more practical problem of generating robust task allocations for identical parallel machines under interval uncertainty in processing times. We start by evaluating the efficacy of current concepts of robustness at capturing the effect of uncertainties. We adopt an axiomatic approach by presenting criteria that must be satisfies for a solution to be considered robust, and show that it is possible to re formulate the problem as a bi-objective optimization task. We demonstrate that an allocation simultaneously achieving a 1.5-approximation in both dimensions exists for the two-agent case, while for the general scenario, a pseudo-polynomial algorithm guarantees a 2-approximation on one dimension and a 2.5-approximation on the other. Extensive computational experiments confirm the practical efficacy and scalability of our approach. In the final part of the thesis, we examine the two-dimensional Balanced Connected Graph Partitioning Problem (2D-BCP), which is a variant of the makespan minimization problem under interval uncertainty in the processing times as well as varying levels of graph connectivity constraints. This problem appears in applications that involve jobs that are spatially distributed in an area of operation, and is best modeled using an underlying graph. For fractional allocations under strict connectivity, we obtain a tight polynomial-time (2,2)-approximation. Relaxing the connectivity constraints, we achieve a refined approximation guarantee of (1 + 1/(λ + 1),1 + 1/(λ + 1)) when each agent is permitted up to 2λ connected components (λ ≥ 1). Integral allocations yield improved approximations from (3,3) under strict connectivity to (2.67,2.67) and (2.5,2.5) with four and six connected components per agent, respectively. These contributions lead to the quantification of the “Price of Connectivity”, and explicitly characterizes how the connectivity constraints affect the existence of solutions and associated algorithms. For each variant of the makespan minimization problem considered in this thesis, we begin with simpler special cases and progressively add complexities to finally build up to the considered problem. This approach leads to interesting insights about the nature of the problems, enables effective characterization, and helps identify the primary sources of their hardness.

Graduation Semester

2025-12

Type of Resource

Thesis

Handle URL

https://hdl.handle.net/2142/132519

Copyright and License Information

Copyright 2025 Raunak Sengupta

Owning Collections