More Like this

1. A competitive algorithm for throughput maximization on identical machines

   https://doi.org/10.1007/S10107-023-02045-0  

   Moseley, Benjamin; Pruhs, Kirk; Stein, Clifford; Zhou, Rudy (July 2024, Mathematical Programming)

   Abstract This paper considers the basic problem of scheduling jobs online with preemption to maximize the number of jobs completed by their deadline onmidentical machines. The main result is anO(1) competitive deterministic algorithm for any number of machines$$m >1$$ $m>1$. 

   more » « less
2. A Theory of Auto-Scaling for Resource Reservation in Cloud Services

   https://doi.org/10.1287/stsy.2021.0091  

   Psychas, Konstantinos; Ghaderi, Javad (February 2022, Stochastic Systems)

   We consider a distributed server system consisting of a large number of servers, each with limited capacity on multiple resources (CPU, memory, etc.). Jobs with different rewards arrive over time and require certain amounts of resources for the duration of their service. When a job arrives, the system must decide whether to admit it or reject it, and if admitted, in which server to schedule it. The objective is to maximize the expected total reward received by the system. This problem is motivated by control of cloud computing clusters, in which jobs are requests for virtual machines (VMs) or containers that reserve resources for various services, and rewards represent service priority of requests or price paid per time unit of service. We study this problem in an asymptotic regime where the number of servers and jobs’ arrival rates scale by a factor L, as L becomes large. We propose a resource reservation policy that asymptotically achieves at least 1/2, and under certain monotone property on jobs’ rewards and resources, at least [Formula: see text] of the optimal expected reward. The policy automatically scales the number of VM slots for each job type as the demand changes and decides in which servers the slots should be created in advance, without the knowledge of traffic rates. 

   more » « less
3. Scheduling with Speed Predictions

   Balkanski, Eric; Ou, Tingting; Stein, Clifford; Wei, Hao-Ting (September 2023, The Workshop on Approximation and Online Algorithms)

   Algorithms with predictions is a recent framework that has been used to overcome pessimistic worst-case bounds in incomplete information settings. In the context of scheduling, very recent work has leveraged machine-learned predictions to design algorithms that achieve improved approximation ratios in settings where the processing times of the jobs are initially unknown. In this paper, we study the speed-robust scheduling problem where the speeds of the machines, instead of the processing times of the jobs, are unknown and augment this problem with predictions. Our main result is an algorithm that achieves a $$\min\{\eta^2(1+\alpha), (2 + 2/\alpha)\}$$ approximation, for any $$\alpha \in (0,1)$$, where $$\eta \geq 1$$ is the prediction error. When the predictions are accurate, this approximation outperforms the best known approximation for speed-robust scheduling without predictions of $2-1/m$, where $$m$$ is the number of machines, while simultaneously maintaining a worst-case approximation of $$2 + 2/\alpha$$ even when the predictions are arbitrarily wrong. In addition, we obtain improved approximations for three special cases: equal job sizes, infinitesimal job sizes, and binary machine speeds. We also complement our algorithmic results with lower bounds. Finally, we empirically evaluate our algorithm against existing algorithms for speed-robust scheduling. 

   more » « less
4. Production Planning for Mass Customization in Additive Manufacturing: Build Orientation Determination, 2D Packing, and Scheduling

   Oh, Yosep; Zhou, Chi; Behdad, Sara (August 2018, Proceedings of the ASME 2018 International Design Engineering Technical Conferences & Computers and Information in Engineering Conference IDETC/CIE 2018 August 26-29, 2018, Quebec, Canada)

   The efficient production planning of Additively Manufactured (AM) parts is a key point for industry-scale adoption of AM. This study develops an AM-based production plan for the case of manufacturing a significant number of parts with different shapes and sizes by multiple machines with the ultimate purpose of reducing the cycle time. The proposed AM-based production planning includes three main steps: (1) determination of build orientation; (2) 2D packing of parts within the limited workspace of AM machines; and (3) scheduling parts on multiple AM machines. For making decision about build orientation, two main policies are considered: (1) laying policy in which the focus is on reducing the height of parts; and (2) standing policy which aims at minimizing the projection area on the tray to reduce the number of jobs. A heuristic algorithm is suggested to solve 2D packing and scheduling problems. A numerical example is conducted to identify which policy is more preferred in terms of cycle time. As a result, the standing policy is more preferred than the laying policy as the number of parts increases. In the case of testing 3,000 parts, the cycle time of standing policy is about 6% shorter than laying policy. 

   more » « less
5. Stochastic Load Balancing on Unrelated Machines

   https://doi.org/10.1287/moor.2019.1049  

   Gupta, Anupam; Kumar, Amit; Nagarajan, Viswanath; Shen, Xiangkun (February 2021, Mathematics of Operations Research)

   null (Ed.)

   We consider the problem of makespan minimization on unrelated machines when job sizes are stochastic. The goal is to find a fixed assignment of jobs to machines, to minimize the expected value of the maximum load over all the machines. For the identical-machines special case when the size of a job is the same across all machines, a constant-factor approximation algorithm has long been known. Our main result is the first constant-factor approximation algorithm for the general case of unrelated machines. This is achieved by (i) formulating a lower bound using an exponential-size linear program that is efficiently computable and (ii) rounding this linear program while satisfying only a specific subset of the constraints that still suffice to bound the expected makespan. We also consider two generalizations. The first is the budgeted makespan minimization problem, where the goal is to minimize the expected makespan subject to scheduling a target number (or reward) of jobs. We extend our main result to obtain a constant-factor approximation algorithm for this problem. The second problem involves q-norm objectives, where we want to minimize the expected q-norm of the machine loads. Here we give an [Formula: see text]-approximation algorithm, which is a constant-factor approximation for any fixed q. 

   more » « less