Publication | Closed Access
On the complexity of scheduling problems for parallel/pipelined machines
77
Citations
9
References
1989
Year
Mathematical ProgrammingEngineeringComputer ArchitectureDedicated ProcessorsComputational ComplexityParallel MetaheuristicsOperations ResearchParallel Complexity TheorySystems EngineeringParallel ComputingCombinatorial OptimizationJob SchedulerOptimal SchedulingComputer EngineeringScheduling (Computing)Computer ScienceInteger ProgrammingScheduling AnalysisScheduling ProblemScheduling (Operating Systems)Scheduling (Production Processes)Parallel ProgrammingReal-time SystemsJob SystemScheduling (Project Management)Resource Optimization
The problem of optimal scheduling of a job system for two dedicated processors is presented. A machine model with two functional units which can be either sequential or pipelined is considered. The complexity of optimal scheduling for a set of expressions on such machines is investigated. Some previous NP-completeness results are reviewed and several new ones are presented. For one restricted case, a polynomial-time algorithm is described and analyzed.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">></ETX>
| Year | Citations | |
|---|---|---|
Page 1
Page 1