Abstract We consider a natural generalization of classical scheduling problems to a setting in which using a time unit for processing a job causes some timedependent cost, the timeofuse tariff, which must be paid in addition to the standard scheduling cost. We focus on preemptive singlemachine scheduling and two classical scheduling cost functions, the sum of (weighted) completion times and the maximum completion time, that is, the makespan. While these problems are easy to solve in the classical scheduling setting, they are considerably more complex when timeofuse tariffs must be considered. We contribute optimal polynomialtime algorithms and best possible approximation algorithms. For the problem of minimizing the total (weighted) completion time on a single machine, we present a polynomialtime algorithm that computes for any given sequence of jobs an optimal schedule, i.e., the optimal set of time slots to be used for preemptively scheduling jobs according to the given sequence. This result is based on dynamic programming using a subtle analysis of the structure of optimal solutions and a potential function argument. With this algorithm, we solve the unweighted problem optimally in polynomial time. For the more general problem, in which jobs may have individual weights, we develop a polynomialtimemore »
Scheduling Stochastic Jobs  Complexity and Approximation Algorithms
Uncertainty is an omnipresent issue in realworld optimization problems. This paper studies a fundamental problem
concerning uncertainty, known as the βrobust scheduling
problem. Given a set of identical machines and a set of jobs
whose processing times follow a normal distribution, the goal
is to assign jobs to machines such that the probability that all
the jobs are completed by a given common due date is maximized. We give the first systematic study on the complexity and algorithms for this problem. A strong negative result
is shown by ruling out the existence of any polynomialtime
algorithm with a constant approximation ratio for the general problem unless P=NP. On the positive side, we provide
the first FPTAS (fixed parameter tractable approximation
scheme) parameterized by the number of different kinds of
jobs, which is a common parameter in scheduling problems.
It returns a solution arbitrarily close to the optimal solution,
provided that the job processing times follow a few different
types of distributions. We further complement the theoretical results by implementing our algorithm. The experiments
demonstrate that by choosing an appropriate approximation
ratio, the algorithm can efficiently compute a nearoptimal
solution.
 Award ID(s):
 2004096
 Publication Date:
 NSFPAR ID:
 10294468
 Journal Name:
 Proceedings of the International Conference on Automated Planning and Scheduling
 ISSN:
 23340843
 Sponsoring Org:
 National Science Foundation
More Like this


Motivated by modern parallel computing applications, we consider the problem of scheduling paralleltask jobs with heterogeneous resource requirements in a cluster of machines. Each job consists of a set of tasks that can be processed in parallel; however, the job is considered completed only when all its tasks finish their processing, which we refer to as the synchronization constraint. Furthermore, assignment of tasks to machines is subject to placement constraints, that is, each task can be processed only on a subset of machines, and processing times can also be machine dependent. Once a task is scheduled on a machine, it requires a certain amount of resource from that machine for the duration of its processing. A machine can process (pack) multiple tasks at the same time; however, the cumulative resource requirement of the tasks should not exceed the machine’s capacity. Our objective is to minimize the weighted average of the jobs’ completion times. The problem, subject to synchronization, packing, and placement constraints, is NPhard, and prior theoretical results only concern much simpler models. For the case that migration of tasks among the placementfeasible machines is allowed, we propose a preemptive algorithm with an approximation ratio of [Formula: see text]. Inmore »

We study the maxmin fairness of multitask jobs in distributed computing platforms. We consider a setting where each job consists of a set of parallel tasks that need to be processed on different servers, and the job is completed once all its tasks finish processing. Each job is associated with a utility which is a decreasing function of its completion time, and captures how sensitive it is to latency. The objective is to schedule tasks in a way that achieves maxmin fairness for jobs' utilities, i.e., an optimal schedule in which any attempt to improve the utility of a job necessarily results in hurting the utility of some other job with smaller or equal utility. We first show a strong result regarding NPhardness of finding the maxmin fair vector of job utilities. The implication of this result is that achieving maxmin fairness in many other distributed scheduling problems (e.g., coflow scheduling) is NPhard. We then proceed to define two notions of approximation solutions: one based on finding a certain number of elements of the maxmin fair vector, and the other based on a singleobjective optimization whose solution gives the maxmin fair vector. We develop scheduling algorithms that provide guarantees undermore »

We study the maxmin fairness of multitask jobs in distributed computing platforms. We consider a setting where each job consists of a set of parallel tasks that need to be processed on different servers, and the job is completed once all its tasks finish processing. Each job is associated with a utility which is a decreasing function of its completion time, and captures how sensitive it is to latency. The objective is to schedule tasks in a way that achieves maxmin fairness for jobs’ utilities, i.e., an optimal schedule in which any attempt to improve the utility of a job necessarily results in hurting the utility of some other job with smaller or equal utility.We first show a strong result regarding NPhardness of finding the maxmin fair vector of job utilities. The implication of this result is that achieving maxmin fairness in many other distributed scheduling problems (e.g., coflow scheduling) is NPhard. We then proceed to define two notions of approximation solutions: one based on finding a certain number of elements of the maxmin fair vector, and the other based on a singleobjective optimization whose solution gives the maxmin fair vector. We develop scheduling algorithms that provide guarantees under thesemore »

Naor, Joseph ; Buchbinder, Niv (Ed.)In the problem of scheduling with nonuniform communication delays, the input is a set of jobs with precedence constraints. Associated with every precedence constraint between a pair of jobs is a communication delay, the time duration the scheduler has to wait between the two jobs if they are scheduled on different machines. The objective is to assign the jobs to machines to minimize the makespan of the schedule. Despite being a fundamental problem in theory and a consequential problem in practice, the approximability of scheduling problems with communication delays is not very well understood. One of the top ten open problems in scheduling theory, in the influential list by Schuurman and Woeginger and its latest update by Bansal, asks if the problem admits a constantfactor approximation algorithm. In this paper, we answer this question in the negative by proving a logarithmic hardness for the problem under the standard complexity theory assumption that NPcomplete problems do not admit quasipolynomialtime algorithms. Our hardness result is obtained using a surprisingly simple reduction from a problem that we call Unique Machine Precedence constraints Scheduling (UMPS). We believe that this problem is of central importance in understanding the hardness of many scheduling problems and wemore »