Ph.D. in Engineering (CSE) at  Veer Surendra Sai University of Technology, Burla, Odisha, India- 768018  (Aug 2016- June 2023). 

        Thesis Title: Studies on Online and Semi-online Scheduling 

Submission: 24th Nov 2022

Defence: 29th June 2023        

Supervisor:  Dr. Rakesh Mohanty, Associate Professor, Dept. of CSE, VSSUT, Burla (Ph.D., IIT, Madras)

Examiners: Dr. Bhawani Sankar Panda, Professor, IIT, Delhi (Indian Examiner) 

  Dr. Zhiyi Tan, Professor, Zhejiang University, China (Foreign Examiner)

➢     Broad Area Of  Research:  Design and Analysis of Algorithms,   ( Text Book )  (Timeline of Algorithms )

➢     Specific Domain: Online Algorithm,  ( Reference Book ) 

➢     Research Problem:   Online Scheduling,    Semi-Online Scheduling

  ABSTRACT

This thesis studies computational hardness, algorithmic competitiveness, and fairness for offline, online, and semi-online variants of the Multiprocessor Scheduling Problem (MPSP). In offline scheduling, an algorithm knows the whole sequence of input jobs at the outset. In online scheduling, an algorithm receives input jobs one after the other and makes an irrevocable scheduling decision on each received job without knowledge of successive jobs. Semi-online scheduling is a variant of online scheduling where an online algorithm schedules a received job with an Extra Piece of Information (EPI) about the entire input job sequence. Online scheduling in a multiuser system allows multiple users to submit their jobs simultaneously. An algorithm here receives at most one job from every user at each time step and irrevocably schedules a batch of jobs before receiving the next batch. The objective is to minimize the makespan of the job schedule. 

Research Motivation: A systematic study to understand the hardness of the offline Multiuser Multiprocessor Scheduling Problem (MUMPSP) with the exploration of the exhaustive solution space is an emerging area of investigation. Although online multiprocessor scheduling has been well-studied in the literature, the design of novel models and constant-competitive online algorithms for online scheduling in multiuser multiprocessor systems have been a potential research challenge. Many authors developed fairness-based performance measures for online scheduling algorithms by considering various resource allocation criteria. However, there is less attention to the design of a user’s objective-based fairness measure. In semi-online scheduling, the non-trivial research challenge is to explore realistic EPI that is essential and sufficient to improve the performance of best-known online scheduling algorithms.

 Contribution: We address the above-mentioned non-trivial research challenges in this xiii thesis. We organize our contribution into four chapters, out of which two are systematic literature surveys on the variants of online and semi-online scheduling, and the other two disseminate our scholarly contribution to advance the state-of-the-art literature. Our survey chapters present well-known algorithms, highlight critical ideas, overview seminal competitive analysis results, and explore non-trivial research challenges. We investigate the hardness, competitiveness, and fairness in offline and online scheduling in a multiuser multiprocessor setting and study the semi-online scheduling problem by considering new EPI parameters. We show the hardness of the MPSP and MUMPSP by alternative reduction techniques with our proposed Scheduling Solution Space Tree (SSST) and Weighted Scheduling Space Tree (WSSST) data structures. We develop a polynomial-time verifier to verify a given solution of MPSP. We design a non-deterministic algorithmic framework named Magic Scheduling (MS) for developing an optimal offline scheduling algorithm. We introduce the Multi List Scheduling (MLS) model to define the online scheduling of parallel submission of jobs. We propose a 2-competitive online algorithm named Largest Job on Least Loaded Machine (LJLLM) for online scheduling over the MLS model. We formally define the Multiuser Multiprocessor Online Scheduling Problem (MUMPOSP) and develop the user’s objective-based fairness model as a new performance measure for online algorithms. In semi-online scheduling, we introduce the k-lookahead model, where an online algorithm foresees the processing times of k successive jobs upon receiving the current job, where k ≥ 1. We design a 4 3 -competitive optimal semi-online algorithm with k = 1 which outperforms the best-known tight bound of 3 2 for online scheduling on 2 identical processors. We obtain the upper bound of 16 11 on the competitive ratio with k = 1 for a 3-identical processor setting. We further achieve a tight bound of 10 9 on the competitive ratio by considering a pair-wise combination of two EPI, where we know at the outset that jobs arrive in decreasing order of their processing times (Decr) and the total sum of processing times of all jobs (Sum). Finally, we highlight open problems and research directions emerging from this thesis as a future scope for further investigation. 

Keywords: Combined EPI, Competitiveness, Fairness, Hardness, Identical machines, Makespan, Lookahead, Multi List, Multiuser, Online, Semi-online, Scheduling. 

Ph.D. Thesis 

 M.Tech in CSE at KIIT University (Institute of Eminence), Bhubaneswar, Odisha, India during 2011- 2013 with 8.61 CGPA (86.1%)

B.Tech in Computer Science and Engineering from B.I.E.T, Bhadrak, BPUT University, Rourkela, Odisha, India,  2006-2010.

Major Project Name: Online Banking   (6 month duration)

 Technical Requirements:

                                                      OS: Windows XP

                                                      Processor: P4 with at least 512 RAM

                                                      Language: C#

                                                      Platform: .NET (ASP environment)

                                                      Database: ORACLE 10g

Objective: The main objective of the project is to create account of customers by providing the related information about the customer and his/her nominee; one can deposit and withdraw money to and from its account in online and also can update personal information as per the guidelines given during the creation of the account. 

C#.net is used as the front end; its tools are used in such a way that it acts as very user friendly and looks good. ASP is used to get support for each and every transaction and different validations, ORACLE 10g database is used as the back end and the commands are used so effectively that the abstraction of data from the database is very fast.

+2 Science with PCBM from Jyoti vihar Junior College, Jyoti vihar, Burla CHSE, Odisha with  70% in 2006.

Matriculation (10th) from Jyoti vihar High School,  Jyoti vihar, Burla, BSE, Odisha with 85% in 2004.

Email: debasis.dwibedy@gmail.com