Single Machine Scheduling with Release Dates
From MaRDI portal
Publication:2784510
DOI10.1137/S089548019936223XzbMath1009.90096OpenAlexW2026040656MaRDI QIDQ2784510
Maurice Queyranne, Michel X. Goemans, Yaoguang Wang, Andreas S. Schulz, Martin Skutella
Publication date: 23 April 2002
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s089548019936223x
Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
Lower bounds for on-line single-machine scheduling., Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs, From the quantum approximate optimization algorithm to a quantum alternating operator ansatz, Unnamed Item, An exact algorithm for the preemptive single machine scheduling of equal-length jobs, A better online algorithm for the parallel machine scheduling to minimize the total weighted completion time, Analysis of bounds for a capacitated single-item lot-sizing problem, Online heuristic for the preemptive single machine scheduling problem of minimizing the total weighted completion time, An exact extended formulation for the unrelated parallel machine total weighted completion time problem, Online scheduling to minimize the total weighted completion time plus the rejection cost, The expected asymptotical ratio for preemptive stochastic online problem, On competitive analysis for polling systems, Joint replenishment meets scheduling, Single machine scheduling with release dates: a distributionally robust approach, An improved greedy algorithm for stochastic online scheduling on unrelated machines, A global constraint for total weighted completion time for unary resources, An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time, Single machine scheduling with job-dependent convex cost and arbitrary precedence constraints, Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem, Online scheduling with linear deteriorating jobs to minimize the total weighted completion time, Approximability of average completion time scheduling on unrelated machines, Resource cost aware scheduling, A 2.542-approximation for precedence constrained single machine scheduling with release dates and total weighted completion time objective, Computation of approximate \(\alpha \)-points for large scale single machine scheduling problem, Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms, On-line scheduling to minimize average completion time revisited., Designing PTASs for MIN-SUM scheduling problems, The asymptotic performance ratio of an on-line algorithm for uniform parallel machine scheduling with release dates, Preemptive scheduling with availability constraints to minimize total weighted completion times, On the relationship between combinatorial and LP-based lower bounds for NP-hard scheduling problems, Almost sure asymptotic optimality for online routing and machine scheduling problems, Online Parallel-Machine Scheduling in KRT Environment to Minimize Total Weighted Completion Time, A \(2.28\)-competitive algorithm for online scheduling on identical machines, LP-based online scheduling: From single to parallel machines, Asymptotical optimality of WSEPT for stochastic online scheduling on uniform machines, Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines, Randomized selection algorithm for online stochastic unrelated machines scheduling, Stochastic Online Scheduling Revisited, Approximation algorithms for shop scheduling problems with minsum objective
