Exploratory research of Lagrangian relaxation for cloud workflow scheduling

Kang, Yoonhwan

Permalink

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

Description

Title

Exploratory research of Lagrangian relaxation for cloud workflow scheduling

Author(s)

Kang, Yoonhwan

Issue Date

2024-07-18

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

Nagi, Rakesh

Department of Study

Industrial&Enterprise Sys Eng

Discipline

Industrial Engineering

Degree Granting Institution

University of Illinois at Urbana-Champaign

Degree Name

M.S.

Degree Level

Thesis

Keyword(s)

• Cloud Workflow Scheduling
• Lagrangian Relaxation (LR)
• Gap Closure Theme
• Subgradient Method.

Abstract

Demand for efficient cloud workflow scheduling solutions is increasing, particularly for managing large-scale datasets. The cloud workflow scheduling problem formulated as a mixed integer linear programming (MILP) problem, requires significant computational time as the dataset scale increases. Consequently, various approaches have been studied to relax the problem into a more solvable form. This thesis presents an exploratory study on applying Lagrangian Relaxation to the cloud workflow scheduling problem. We propose a MILP formulation incorporating moving costs to reflect real-world scenarios better. By applying the Lagrangian relaxation approach and additional methods, we can obtain tight near-optimal solutions quickly. These solutions can serve as lower bounds for the MILP, enabling a reduction in computational time.

Graduation Semester

2024-08

Type of Resource

Thesis

Handle URL

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

Copyright and License Information

Copyright 2024 Yoonhwan Kang

Owning Collections