Exploratory research of Lagrangian relaxation for cloud workflow scheduling

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.

Name thesis:degree_name

M.S.

Level thesis:degree_level

Thesis

Discipline thesis:degree_discipline

Industrial Engineering

Grantor

University of Illinois at Urbana-Champaign

Year dc:date

2024

Author dc:creator

• Kang, Yoonhwan

Contributors dc:contributor

• Nagi, Rakesh

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

Statement dc:rights

• Copyright 2024 Yoonhwan Kang

Language dc:language

en, eng

Handle dc:identifier

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

OAI record oai:identifier

https://www.ideals.illinois.edu/oai-pmh?verb=GetRecord&metadataPrefix=etdms&identifier=oai%3Awww.ideals.illinois.edu%3A2142%2F125638