Online scheduling of jobs with favorite machines
From MaRDI portal
Publication:2289948
Abstract: This work introduces a natural variant of the online machine scheduling problem on unrelated machines, which we refer to as the favorite machine model. In this model, each job has a minimum processing time on a certain set of machines, called favorite machines, and some longer processing times on other machines. This type of costs (processing times) arise quite naturally in many practical problems. In the online version, jobs arrive one by one and must be allocated irrevocably upon each arrival without knowing the future jobs. We consider online algorithms for allocating jobs in order to minimize the makespan. We obtain tight bounds on the competitive ratio of the greedy algorithm and characterize the optimal competitive ratio for the favorite machine model. Our bounds generalize the previous results of the greedy algorithm and the optimal algorithm for the unrelated machines and the identical machines. We also study a further restriction of the model, called the symmetric favorite machine model, where the machines are partitioned equally into two groups and each job has one of the groups as favorite machines. We obtain a 2.675-competitive algorithm for this case, and the best possible algorithm for the two machines case.
Recommendations
Cites work
- A Better Algorithm for an Ancient Scheduling Problem
- Better Bounds for Online Scheduling
- Bounds for Certain Multiprocessing Anomalies
- Bounds for List Schedules on Uniform Processors
- Competitive two-agent scheduling and its applications
- Equilibria for two parallel links: the strong price of anarchy versus the price of anarchy
- scientific article; zbMATH DE number 4130003 (Why is no real title available?)
- scientific article; zbMATH DE number 742966 (Why is no real title available?)
- Makespan minimization in online scheduling with machine eligibility
- Mechanism design for decentralized online machine scheduling
- Mechanisms for scheduling with single-bit private values
- New algorithms for an ancient scheduling problem.
- On-Line Load Balancing for Related Machines
- On-line load balancing in a hierarchical server topology
- On-line load balancing made simple: greedy strikes back
- On-line routing of virtual circuits with applications to load balancing and machine scheduling
- On-line scheduling of two parallel machines with a single server
- On-line scheduling revisited
- Online scheduling of mixed CPU-GPU jobs
- Online scheduling of two job types on a set of multipurpose machines with unit processing times
- Randomized on-line scheduling on two uniform machines
- Scheduling problems on two sets of identical machines
- Selfish jobs with favorite machines: price of anarchy vs. strong price of anarchy
- Selfish load balancing for jobs with favorite machines
- Truthful mechanism design for multidimensional scheduling via cycle monotonicity
Cited in
(6)- Applying ``peeling onion approach for competitive analysis in online scheduling with rejection
- An optimal online algorithm for single-processor scheduling problem with learning effect
- Online scheduling with deterioration and unexpected processor breakdown
- Online optimisation for ambulance routing in disaster response with partial or no information on victim conditions
- Online single-processor scheduling with an unexpected breakdown
- Coordination mechanisms for scheduling selfish jobs with favorite machines
This page was built for publication: Online scheduling of jobs with favorite machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2289948)
