In my PhD thesis my research focus is on the design and analysis of algorithms for scheduling jobs on parallel processors/servers. A processor may represent a server, sensor, or storage unit, while a job may represent a computational task, sensor, or read/write request. Even though it is an age old problem, my interest is in the new paradigms under which the problem arises in contemporary computing and networking applications. In the following I discuss the paradigms I study, namely, placement constraints and multi-processor requirement of jobs, and semi-online job scheduling.

The job

Jaya Prakash Champati and Ben Liang, "

Jaya Prakash Champati and Yossi Azar and Ben Liang, "

Utility computing or cloud computing has paved way to a wide variety of hybrid computing systems
(e.g., hybrid cloud, Mobile Cloud Computing (MCC) system etc.). A common aspect in all these
systems is that computational tasks are processed in different environments (e.g. locally, remotely). Using parallel processor scheduling in a semi-online setting, we model and optimize task schedulers in such systems.

Jaya Prakash Champati and Ben Liang, "

Jaya Prakash Champati and Ben Liang, "

Jaya Prakash Champati and Ben Liang, "

Jaya Prakash Champati and Ben Liang, "

Jaya Prakash Champati and Ben Liang, "

Jaya Prakash Champati and Ben Liang, "

Jaya Prakash Champati and Ben Liang, "

Jaya Prakash Champati and Prasanna Chaporkar, "

Jaya Prakash Champati and Prasanna Chaporkar, "

**Job placement constraints and multi-processor requirement**

*placement constraints*, where a job is allowed to schedule only on a subset of processors, is a common requirement in current computing and information systems (e.g., HDFS and Map-reduce systems) and in several networking applications. Also, in some of these systems a job may require processing on more than one processor although not necessarily simultaneously, which we call*multi-processor requirement*.Jaya Prakash Champati and Ben Liang, "

*Efficient minimization of sum and differential costs on machines with job placement constraints*", in Proc.IEEE INFOCOM 2017, Atlanta, GA, May 2017.**Summary:**In this work we revisited the fundamental problem of assigning n jobs to m processors, where jobs are identical and have placement constraints. The processors are heterogeneous in the sense that each processor is associated with a different value of some attribute, e.g., processing speed, energy, or bandwidth. In contrast to the previous works we considered a general objective of minimizing the sum of g_{i}(k), where g_{i}(k) is a general convex cost function associated with the ith machine, and k is the number of jobs assigned to the machine. Further, we studied the problem of minimizing the maximum differential cost given by max_{i}g_{i}(k) - g_{i}(k-1). An interesting result we show is that minimizing the sum cost minimizes the maximum differential cost. The result can be used for solving the maximum differential cost problem in several networking applications.

__Unpublished Work__:Jaya Prakash Champati and Yossi Azar and Ben Liang, "

*2-Approximation Algorithm for a Generalization of Scheduling on Unrelated Parallel Machines*", manuscript under submission, Information Processing Letters, Elsivier.**Summary:**In this work we consider the jobs are not identical, have placement constraints and multi-processor requirement. Under this model we propose a 2-approximation algorithm for solving the makespan minimization problem.**Semi-online scheduling algorithms**

__Publications__:Jaya Prakash Champati and Ben Liang, "

*Single restart with time stamps for computational offloading in a semi-online setting*", to appear in IEEE INFOCOM 2017, Atlanta, GA, May 2017.**Summary:**We studied the problem of scheduling n jobs on m+m' parallel processors, where the processing times on m local processors are known while those on the remaining m' remote processors are not known a priori. The m processors may model parallel CPU cores in a local device (e.g. smartphone, tablet etc.) or processors in a local computing cluster. The remote processors may represent computational servers whose help is enlisted by the local device or the local cluster. We initially focused on the case m' = 1 and proposed a semi-online algorithm termed Single Restart with Time Stamps (SRTS), which has time complexity O(n log n). SRTS has O(1) competitive ratio when the processing times are independent of m and asymptotically constant competitive ratio in practice when the processing times are dependent on m. We extended the ideas of SRTS and proposed a heuristic algorithm termed SRTS-Multiple (SRTS-M) for the case m' > 1.Jaya Prakash Champati and Ben Liang, "

*Single restart with time stamps for parallel task processing with known and unknown processors*", manuscript under submission, IEEE Transactions on Computers.Jaya Prakash Champati and Ben Liang, "

*One-restart algorithm for scheduling and offloading in a hybrid cloud*", in Proc. IEEE/ACM International Symposium on Quality of Service (IWQoS), Jun. 2015. PDF**Summary:**Given that the task processing times are not known a priori, we propose an**O(√m) competitive algorithm**for minimizing the weighted sum of makespan of tasks plus the cost of the offloaded tasks, where m is number of parallel processors. An interesting by-product result of the proposed approach is a 4-competitive algorithm for makespan minimization problem on**two unrelated processors**, where the processing times of tasks on one processor are known and the other processor are unknown.Jaya Prakash Champati and Ben Liang, "

*Delay and Cost Optimization in Computational Offlaoding Systems with Unkown Processing Times*", manuscript under submission, IEEE Transactions on Parallel and Distributed Computing (TPDS).Jaya Prakash Champati and Ben Liang, "

*Semi-online task partitioning and communication between local and remote processors*", in Proc. IEEE International Conference on Cloud Networking (CloudNet), Oct. 2015. PDF**Summary:**In this work, we study task offloading between a local processor and a related remote processor, where tasks offloaded to the remote processor incur non-negligible**communication delay**. Given that the processing times of the tasks are not known a priori, and the communication times of the tasks are smaller than their corresponding processing times at the remote processor, we propose an**(1+√5)/2 competitive algorithm**for minimizing makespan of the tasks.Jaya Prakash Champati and Ben Liang, "

*Semi-online Algorithms for Computational Task Offloading with Communication Delay*", IEEE Transactions on Parallel and Distributed Computing (TPDS), vol 28, no. 4, pp. 1189-1201, Apr. 2017. PDF**Summary:**In this paper we build on the results presented in the above conference paper. We propose yet another algorithm and show that it is**5-competitive**for the case where the communication times of the tasks are lager than their corresponding processing times at the remote processor. We also provide competitive ratios for both the proposed algorithms under general communication and processing times of the tasks.**Other Publications**

Jaya Prakash Champati and Ben Liang, "

*Energy Compensated Cloud Assistance in Mobile Cloud Computing*", in Proc. IEEE INFOCOM Workshop, April 2014, pp. 392-397. PDFJaya Prakash Champati and Prasanna Chaporkar, "

*Proportionally Fair Resource Allocation in Multi-Rate Wireless LANs*", in Proc. 17th IEEE National Conference on Communications (NCC), 2011.(**BEST PAPER AWARD**). PDFJaya Prakash Champati and Prasanna Chaporkar, "

*Proportionally Fair Resource Allocation in Multi-Rate Wireless LANs*", manuscript under revision, IEEE Transactions on Control of Network Systems (TCNS). PDF