NP-complete scheduling problems
From MaRDI portal
Publication:1220386
DOI10.1016/S0022-0000(75)80008-0zbMath0313.68054MaRDI QIDQ1220386
Publication date: 1975
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Related Items (only showing first 100 items - show all)
ON CONSIDERING COMMUNICATION IN SCHEDULING TASK GRAPHS ON PARALLEL PROCESSORS ⋮ ON OPTIMAL LOOP UNROLLING IN TWO-PROCESSOR SCHEDULING ⋮ SCHEDULING INTERVAL ORDERS IN PARALLEL ⋮ A quest for a fair schedule: the international Young Physicists' Tournament ⋮ Speeding-up parallel computation of large smooth-degree isogeny using precedence-constrained scheduling ⋮ Computational task offloading algorithm based on deep reinforcement learning and multi-task dependency ⋮ Scheduling Massively Parallel Multigrid for Multilevel Monte Carlo Methods ⋮ Block structured scheduling using constraint logic programming ⋮ PERMUTATION-BASED GENETIC, TABU, AND VARIABLE NEIGHBORHOOD SEARCH HEURISTICS FOR MULTIPROCESSOR SCHEDULING WITH COMMUNICATION DELAYS ⋮ PREEMPTIVE SCHEDULING ON PARALLEL PROCESSORS WITH DUE DATES ⋮ Performance of critical path type algorithms for scheduling on parallel processors ⋮ Fast parallel heuristics for the job shop scheduling problem ⋮ Unnamed Item ⋮ Unnamed Item ⋮ TWO CONP-COMPLETE SCHEDULE ANALYSIS PROBLEMS ⋮ Profile Scheduling of Opposing Forests and Level Orders ⋮ A multi-objective memetic algorithm for the job-shop scheduling problem ⋮ Minimizing lateness for precedence graphs with constant delays on dedicated pipelined processors ⋮ Controlling the data space of tree structured computations ⋮ Analysis of scheduling problems with typed task systems ⋮ Applications of scheduling theory to formal language theory ⋮ A state-space search approach for parallel processor scheduling problems with arbitrary precedence relations ⋮ Resource-constrained multi-project scheduling with tardy costs: Comparing myopic, bottleneck, and resource pricing heuristics ⋮ Scheduling with constrained processor allocation for interval orders ⋮ A novel threshold accepting meta-heuristic for the job-shop scheduling problem ⋮ Nearly on line scheduling of preemptive independent tasks ⋮ On the Complexity of Scheduling to Optimize Average Response Time ⋮ Parallel AFMPB solver with automatic surface meshing for calculation of molecular solvation free energy ⋮ On the worst-case ratio of a compound multiprocessor scheduling algorithm ⋮ UET scheduling with unit interprocessor communication delays ⋮ Scheduling of conditional executed jobs on unrelated processors ⋮ Multiprocessor scheduling with interprocessor communication delays ⋮ Scheduling tasks with communication delays on parallel processors ⋮ Minimizing the number of stations and station activation costs for a production line ⋮ AN EFFECTIVE APPROACH FOR DISTRIBUTED PROGRAM ALLOCATION ⋮ Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints ⋮ Scheduling tree-structured tasks with restricted execution times ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints ⋮ The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays ⋮ Decidable, polynomial-time, and np-complete cases of the isotone bipartite graph problem ⋮ Scheduling unit-length jobs with precedence constraints of small height ⋮ A branch-and-bound algorithm to solve the equal-execution-time job scheduling problem with precedence constraint and profile ⋮ Parallel batch scheduling of equal-length jobs with release and due dates ⋮ Hypervolume indicator and dominance reward based multi-objective Monte-Carlo tree search ⋮ An improved coral reef optimization-based scheduling algorithm for cloud computing ⋮ Probabilistic quality estimations for combinatorial optimization problems ⋮ Fast combination of scheduling chains under resource and time constraints ⋮ Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates ⋮ Open shop problems with unit time operations ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ An iterative algorithm for scheduling UET tasks with due dates and release times. ⋮ Discrete optimization with polynomially detectable boundaries and restricted level sets ⋮ Energy-efficient real-time scheduling for two-type heterogeneous multiprocessors ⋮ Scheduling chained multiprocessor tasks onto large multiprocessor system ⋮ Lower-bound complexity algorithm for task scheduling on heterogeneous grid ⋮ Parallel machine problems with equal processing times: a survey ⋮ Scheduling in a dynamic heterogeneous distributed system using estimation error ⋮ A natural quadratic approach to the generalized graph layering problem ⋮ Non-approximability of precedence-constrained sequencing to minimize setups. ⋮ A dynamic rescheduling algorithm for resource management in large scale dependable distributed systems ⋮ Scheduling batches on parallel machines with major and minor set-ups ⋮ A genetic algorithm approach to high-level synthesis of digital circuits ⋮ An experimental analysis of local minima to improve neighbourhood search. ⋮ A state-of-the-art review of parallel-machine scheduling research ⋮ Scheduling with limited machine availability ⋮ A Comparison of Random Task Graph Generation Methods for Scheduling Problems ⋮ Modeling Block Structured Project Scheduling with Resource Constraints ⋮ Scheduling on a hypercube ⋮ Performance of Garey-Johnson algorithm for pipelined typed tasks systems ⋮ Algorithms for scheduling with integer preemptions on parallel machines to minimize the maximum lateness ⋮ A metric approach for scheduling problems with minimizing the maximum penalty ⋮ Scheduling with neural networks -- the case of the Hubble Space Telescope ⋮ Scheduling with bully selfish jobs ⋮ Analysis and optimisation of hierarchically scheduled multiprocessor embedded systems ⋮ Scheduling with uncertainties on new computing platforms ⋮ Scheduling \(UET\)-tasks on a star network: complexity and approximation ⋮ Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems ⋮ Graph layering by promotion of nodes ⋮ Scheduling two-machine no-wait open shops to minimize makespan ⋮ The worst-case analysis of the Garey-Johnson algorithm ⋮ Scheduling tasks with exponential duration on unrelated parallel machines ⋮ Scheduling DAG-based applications in multicluster environments with background workload using task duplication ⋮ Optimal scheduling of homogeneous job systems ⋮ Ideal schedules in parallel machine settings ⋮ Polyhedral results for position-based scheduling of chains on a single machine ⋮ Preemptive scheduling with variable profile, precedence constraints and due dates ⋮ On scheduling multi-processor systems with algebraic objectives ⋮ Two simulated annealing-based heuristics for the job shop scheduling problem ⋮ A hybrid heuristic of variable neighbourhood descent and great deluge algorithm for efficient task scheduling in grid computing ⋮ NP-Complete operations research problems and approximation algorithms ⋮ Task scheduling with and without communication delays: A unified approach ⋮ Effective solution of certain problems of theory of schedulings of nets ⋮ On some implementations of solving the resource constrained project scheduling problems ⋮ Upper bound of the duration of the shortest schedule in one class of Hu problems ⋮ Makespan minimization with OR-precedence constraints ⋮ On-line Scheduling with Optimal Worst-Case Response Time ⋮ Parallelization of automata
Cites Work
This page was built for publication: NP-complete scheduling problems
