Shared multi-processor scheduling

DOI10.1016/J.EJOR.2017.03.002zbMATH Open1403.90317arXiv1607.06021OpenAlexW2502805255MaRDI QIDQ1753597FDOQ1753597

Authors: Dariusz Dereniowski, Wieslaw Kubiak 

Publication date: 29 May 2018

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Scheduling for parallel processing
• A new continuous model for job-shop scheduling
• Decentralized subcontractor scheduling with divisible jobs

Cited In (10)

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

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)