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
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, Heuristics for unrelated machine scheduling with precedence constraints, Single machine scheduling subject to precedence delays, Effective optimization methods for single-machine scheduling (survey), Scheduling with or without precedence relations on a serial-batch machine to minimize makespan and maximum cost, Scheduling Opposing Forests, Scheduling preemptive jobs with precedence constraints on parallel machines, Optimal scheduling on parallel machines for a new order class, Lower bounds on precedence-constrained scheduling for parallel processors., First fit decreasing scheduling on uniform multiprocessors, On scheduling cycle shops: Classification, complexity and approximation, On the complexity of a family of generalized matching problems, Scheduling of parallel programs on configurable multiprocessors by genetic algorithms, On the complexity of scheduling unit-time jobs with or-precedence constraints, Two deadline reduction algorithms for scheduling dependent tasks on parallel processors, An efficient deterministic parallel algorithm for two processors precedence constraint scheduling
Cites Work
