Two-Processor Scheduling with Start-Times and Deadlines

DOI10.1137/0206029zbMath0369.90053OpenAlexW2001364911WikidataQ94701355 ScholiaQ94701355MaRDI QIDQ4146529

Publication date: 1977

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0206029

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Deterministic scheduling theory in operations research (90B35)

Related Items

An $\mathcal{O}(\log {m})$-Competitive Algorithm for Online Machine Minimization, Breaking 1 - 1/e Barrier for Nonpreemptive Throughput Maximization, Scheduling with tails and deadlines, Single machine scheduling with release times, deadlines and tardiness objectives, Efficient web searching using temporal factors, Scheduling with forbidden sets, Throughput scheduling with equal additive laxity, Throughput scheduling with equal additive laxity, Multilevel Planarity, Scheduling Opposing Forests, Tree scheduling with communication delays, Some complexity results about threshold graphs, Equivalent approximation algorithms for node cover, Computing maximum mean cuts, Shelf algorithms for on-line strip packing, Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem, A simplified NP-complete MAXSAT problem, Data sufficiency for queries on cache, On the complexity of Boolean unification, Encryption using Hungarian rings, Effective iterative algorithms in scheduling theory, Some results of the relocation problems with processing times and deadlines, Boolean minors, On an approximation measure founded on the links between optimization and polynomial approximation theory, Solving the traveling repairman problem on a line with general processing times and deadlines, Efficient algorithms for scheduling parallel jobs with interval constraints in clouds, On semi-$P_ 4$-sparse graphs, Performance evaluation of concurrent systems using conflict-free and persistent Petri nets, Flexible open shop scheduling problem to minimize makespan, The equivalence of two classical list scheduling algorithms for dependent typed tasks with release dates, due dates and precedence delays, Partitions of graphs into one or two independent sets and cliques, k-optimal solution sets for some polynomially solvable scheduling problems, Two-segmented channel routing is strong NP-complete, Linear logic for nets with bounded resources, The complexity of planar graph choosability, Interior and exterior functions of Boolean functions, The complexity of generalized graph colorings, Equational unification, word unification, and 2nd-order equational unification, An improved algorithm for online machine minimization, Open shop problems with unit time operations, The complexity of changing colourings with bounded maximum degree, 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., Embedding hypercubes into cylinders, snakes and caterpillars for minimizing wirelength, Coordinated scheduling of production and delivery with production window and delivery capacity constraints, Universal number partition problem with divisibility, Solving the resource constrained deadline scheduling problem via reduction to the network flow problem, Open neighborhood locating-dominating in trees, How well can a graph be n-colored?, Normal-form preemption sequences for an open problem in scheduling theory, Balancing signed graphs, Probabilistic single processor scheduling, Scheduling independent jobs with stochastic processing times and a common due date on parallel and identical machines, NP-completeness of some generalizations of the maximum matching problem, A model for minimizing active processor time, Computing independent sets in graphs with large girth, Performance of Garey-Johnson algorithm for pipelined typed tasks systems, Finding efficient make-to-order production and batch delivery schedules, Bounded vertex colorings of graphs, Reconstructing sets of orthogonal line segments in the plane, No-hole $(r+1)$-distant colorings, Hamiltonian cycle is polynomial on cocomparability graphs, Reversible iterative graph processes, Shiftable intervals, The external constraint 4 nonempty part sandwich problem, Parameterized complexity of coloring problems: treewidth versus vertex cover, Approximating a vehicle scheduling problem with time windows and handling times, Robust network optimization under polyhedral demand uncertainty is $NP$-hard, Absolute retracts and varieties generated by chordal graphs, A review of exact solution methods for the non-preemptive multiprocessor flowshop problem, Irreversible conversion of graphs, Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources, Approximation algorithms for variable voltage processors: min energy, max throughput and online heuristics, The worst-case analysis of the Garey-Johnson algorithm, Single machine scheduling to minimize maximum lateness subject to release dates and precedence constraints, A polyhedral study of the asymmetric traveling salesman problem with time windows, On the complexity of the independent set problem in triangle graphs, A polynomial-time scheduling approach to minimise idle energy consumption: an application to an industrial furnace, Ideal schedules in parallel machine settings, Fall colouring of bipartite graphs and Cartesian products of graphs, Deadline scheduling of tasks with ready times and resource constraints, On the depth of combinatorial optimization problems, On Ringeisen's isolation game, Fixed edge-length graph drawing is NP-hard, Scheduling for multi-robot routing with blocking and enabling constraints, A study of the application of Kohonen-type neural networks to the travelling salesman problem, On approximation problems related to the independent set and vertex cover problems, Recognizing graphs with fixed interval number is NP-complete, On ${\mathbb{K}}^{\Delta}$, On the r,s-SAT satisfiability problem and a conjecture of Tovey, An algebraic point of view of the data structures of database systems, On the minimum label spanning tree problem, An efficient algorithm for finding ideal schedules, Approximation Algorithms for Variable Voltage Processors: Min Energy, Max Throughput and Online Heuristics, On a multiconstrained model for chromatic scheduling, Hamiltonian paths in Cayley graphs, Distance graphs and the $T$-coloring problem, A note on a theorem by Ladner, Arbres avec un nombre maximum de sommets pendants, On the intractability of preemptive single-machine job scheduling with release times, deadlines, and family setup times, Approximations to clustering and subgraph problems on trees, On the complexity of partitioning graphs into connected subgraphs, On budget-constrained flow improvement., Embeddings of graphs, Bibliography on domination in graphs and some basic definitions of domination parameters, Performance evaluation of systems of cyclic sequential processes with mutual exclusion using Petri nets, Sharing jugs of wine, The $k$-SATISFIABILITY problem remains NP-complete for dense families, Algorithms for dynamic scheduling of unit execution time tasks, Two deadline reduction algorithms for scheduling dependent tasks on parallel processors