Shared processor scheduling

DOI10.1007/S10951-018-0566-0MaRDI QIDQ2317136zbMATH OpenOpenAlexFDO

Authors Dariusz Dereniowski, Wieslaw Kubiak

Publication date 8 August 2019

Published in Journal of Scheduling (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1704.06361

zbMATH Keywords

schedulingdivisible jobsshared processor

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: We study the shared processor scheduling problem with a single shared processor where a unit time saving (weight) obtained by processing a job on the shared processor depends on the job. A polynomial-time optimization algorithm has been given for the problem with equal weights in the literature. This paper extends that result by showing an $O(nlogn)$ optimization algorithm for a class of instances in which non-decreasing order of jobs with respect to processing times provides a non-increasing order with respect to weights --- this instance generalizes the unweighted case of the problem. This algorithm also leads to a $frac12$-approximation algorithm for the general weighted problem. The complexity of the weighted problem remains open.

Recommendations

• Shared processor scheduling of multiprocessor jobs
• Shared multi-processor scheduling
• scientific article; zbMATH DE number 67289
• Single processor scheduling with job values depending on their completion times
• Scheduling jobs on heterogeneous processors

Cites work

• A new continuous model for job-shop scheduling
• Approximation algorithms for multi-agent scheduling to minimize total weighted completion time
• Decentralized subcontractor scheduling with divisible jobs
• Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs
• Multiagent scheduling. Models and algorithms
• Shared multi-processor scheduling

Cited in

(3)

• Shared multi-processor scheduling
• A parallel-machine scheduling problem with an antithetical property to maximize total weighted early work
• Shared processor scheduling of multiprocessor jobs

This page was built for publication: Shared processor scheduling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2317136)