Shared multi-processor scheduling

DOI10.1016/J.EJOR.2017.03.002MaRDI QIDQ1753597zbMATH OpenOpenAlexFDO

Authors Dariusz Dereniowski, Wieslaw Kubiak

Publication date 29 May 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

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

zbMATH Keywords

combinatorial optimizationsupply chainssubcontractingdivisible jobsshared processors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: We study shared multi-processor scheduling problem where each job can be executed on its private processor and simultaneously on one of many processors shared by all jobs in order to reduce the job's completion time due to processing time overlap. The total weighted overlap of all jobs is to be maximized. The problem models subcontracting scheduling in supply chains and divisible load scheduling in computing. We show that synchronized schedules that complete each job at the same time on its private processor and shared processors, if any is actually used by the job, include optimal schedules. We prove that the problem is NP-hard in the strong sense for jobs with arbitrary weights, and we give an efficient, polynomial-time algorithm for the problem with equal weights.

Recommendations

• Shared processor scheduling of multiprocessor jobs
• Shared processor scheduling
• scientific article; zbMATH DE number 67289
• Multiprocessor scheduling with machine allotment and parallelism constraints
• scientific article; zbMATH DE number 1271325

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3073200 (Why is no real title available?)
• A new continuous model for job-shop scheduling
• Decentralized subcontractor scheduling with divisible jobs
• Scheduling for parallel processing

Cited in

(10)

• Exact algorithms for scheduling programs with shared tasks
• Shared processor scheduling
• Multitasking scheduling with shared processing
• Greedy multiprocessor server scheduling
• Shared processor scheduling of multiprocessor jobs
• Guest editorial: Multiprocessor scheduling
• Scheduling with divisible jobs and subcontracting option
• Survey of scheduling techniques for addressing shared resources in multicore processors
• Streaming algorithms for multitasking scheduling with shared processing
• Provably good multiprocessor scheduling with resource sharing

This page was built for publication: Shared multi-processor scheduling

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