scientific article

Alexander H. G. Rinnooy Kan, Jacques Labetoulle, Eugene L. Lawler, Jan Karel Lenstra

Publication date: 1984

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

parallel machines NP-hardness maximum completion time polynomial-time algorithms maximum lateness total weighted completion time optimal preemptive schedules release dates for the jobs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Related Items (62)

Lower bounds for on-line single-machine scheduling. ⋮ Minimizing the stretch when scheduling flows of divisible requests ⋮ Nearly on line scheduling of preemptive independent tasks ⋮ Scheduling jobs that arrive over time ⋮ An exact algorithm for the preemptive single machine scheduling of equal-length jobs ⋮ Online weighted flow time and deadline scheduling ⋮ Parallel machine scheduling with machine availability and eligibility constraints ⋮ An effective lower bound on \(L_{\max}\) in a worker-constrained job shop ⋮ Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time ⋮ Preemptive scheduling on uniformly related machines: minimizing the sum of the largest pair of job completion times ⋮ Scheduling machine-dependent jobs to minimize lateness on machines with identical speed under availability constraints ⋮ Efficient computation of optimal energy and fractional weighted flow trade-off schedules ⋮ An \(O( n^2)\) algorithm for scheduling equal-length preemptive jobs on a single machine to minimize total tardiness ⋮ On the Complexity of Speed Scaling ⋮ Is a unit-job shop not easier than identical parallel machines? ⋮ Single machine batch scheduling with release times and delivery costs ⋮ Preemptive online scheduling with rejection of unit jobs on two uniformly related machines ⋮ Open shop problems with unit time operations ⋮ Competitive kill-and-restart and preemptive strategies for non-clairvoyant scheduling ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ Power of Preemption for Minimizing Total Completion Time on Uniform Parallel Machines ⋮ Competitive two-agent scheduling with release dates and preemption on a single machine ⋮ Preemptive scheduling of equal-length jobs in polynomial time ⋮ Scheduling periodically occurring tasks on multiple processors ⋮ Generalizing Horn's conditions for preemptive scheduling on identical parallel machines via network flow techniques ⋮ Parallel machine problems with equal processing times: a survey ⋮ Minimizing total tardiness on parallel machines with preemptions ⋮ Single-machine scheduling with no idle time and release dates to~minimize a regular criterion ⋮ Preemptive scheduling to minimize mean weighted flow time ⋮ Multi-project scheduling problem under shared multi-skill resource constraints ⋮ Scheduling open shops with parallel machines ⋮ A competitive two-agent scheduling problem on parallel machines with release dates and preemption ⋮ An algorithm for single machine sequencing with release dates to minimize total weighted completion time ⋮ Surrogate duality relaxation for job shop scheduling ⋮ Scheduling with limited machine availability ⋮ Preemptive scheduling on uniform parallel machines with controllable job processing times ⋮ Scheduling multiprocessor tasks for mean flow time criterion ⋮ Online scheduling with linear deteriorating jobs to minimize the total weighted completion time ⋮ Fair Scheduling via Iterative Quasi-Uniform Sampling ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ Branch-and-bound method for minimizing the weighted completion time scheduling problem on a single machine with release dates ⋮ On-line scheduling to minimize average completion time revisited. ⋮ The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates ⋮ Jackson's pseudo-preemptive schedule and cumulative scheduling problems ⋮ Optimal parallel machines scheduling with availability constraints ⋮ Scheduling a single machine to minimize a regular objective function under setup constraints ⋮ Ideal schedules in parallel machine settings ⋮ Single-machine hierarchical scheduling with release dates and preemption to minimize the total completion time and a regular criterion ⋮ Modeling single machine preemptive scheduling problems for computational efficiency ⋮ Shop scheduling problems with pliable jobs ⋮ Preemptive scheduling of multiprocessor tasks on the dedicated processor system subject to minimal lateness ⋮ Preemptive scheduling on uniform machines to minimize mean flow time ⋮ Malleable scheduling for flows of jobs and applications to MapReduce ⋮ Lower and Upper Bounds for the Preemptive Single Machine Scheduling Problem with Equal Processing Times ⋮ Integrality Property in Preemptive Parallel Machine Scheduling ⋮ Minimizing average completion time in the presence of release dates ⋮ Scheduling uniform machines on-line requires nondecreasing speed ratios ⋮ A 1. 47-approximation for a preemptive single-machine scheduling problem ⋮ A Tight 2-Approximation for Preemptive Stochastic Scheduling ⋮ Mathematical programming formulations for machine scheduling: A survey ⋮ The flow shop with parallel machines: A tabu search approach ⋮ An improved max-flow-based lower bound for minimizing maximum lateness on identical parallel machines

This page was built for publication: