Shared processor scheduling

DOI10.1007/S10951-018-0566-0zbMATH Open1420.90019arXiv1704.06361OpenAlexW2609401311MaRDI QIDQ2317136FDOQ2317136

Authors: Dariusz Dereniowski, Wieslaw Kubiak 

Publication date: 8 August 2019

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

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.

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

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

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)

Cites Work

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

Cited In (3)

• A parallel-machine scheduling problem with an antithetical property to maximize total weighted early work
• Shared multi-processor scheduling
• 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)