Semi on-line algorithms for the partition problem

DOI10.1016/S0167-6377(98)00005-4zbMath0908.90165OpenAlexW2021598206WikidataQ126789373 ScholiaQ126789373MaRDI QIDQ1267197

Vladimir Kotov, Zsolt Tuza, Maria Grazia Speranza, Hans Kellerer

Publication date: 3 December 1998

Published in: Operations Research Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0167-6377(98)00005-4

zbMATH Keywords

heuristic NP-complete worst-case ratio partition problem semi on-line versions

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items

A survey on makespan minimization in semi-online environments, Single machine scheduling with job delivery to multiple customers, Online makespan minimization with parallel schedules, \(\kappa\)-partitioning problems for maximizing the minimum load, Semi-online scheduling on two identical machines with a common due date to maximize total early work, Scheduling with testing on multiple identical parallel machines, Optimal preemptive semi-online scheduling on two uniform processors, Semi on-line scheduling on three processors with known sum of the tasks, A note on on-line scheduling with partial information, SEMI-ONLINE MACHINE COVERING, Better Algorithms for Online Bin Stretching, Online algorithms with advice for the dual bin packing problem, Tight upper bounds for semi-online scheduling on two uniform machines with known optimum, Linear time algorithms for parallel machine scheduling, Semi-online machine covering on two uniform machines with known total size, Online and semi-online scheduling of two machines under a grade of service provision, ONLINE MINIMUM MAKESPAN SCHEDULING WITH A BUFFER, Optimal semi-online algorithms for machine covering, Semi-online scheduling for jobs with release times, Semi-online scheduling: a survey, Semi-online scheduling problems on two identical machines with inexact partial information, A two-phase algorithm for bin stretching with stretching factor 1.5, Semi-online hierarchical scheduling for \(l_p\)-norm load balancing with buffer or rearrangements, Semi-online scheduling with two GoS levels and unit processing time, Improved semi-online makespan scheduling with a reordering buffer, Semi-online scheduling problems on a small number of machines, Semi-online early work maximization problems on two hierarchical uniform machines with partial information of processing time, Bin stretching with migration on two hierarchical machines, Parallel solutions for preemptive makespan scheduling on two identical machines, Optimal semi-online algorithm for scheduling with rejection on two uniform machines, Online scheduling with rearrangement on two related machines, Online early work maximization on three hierarchical machines with a common due date, Parallel solutions for ordinal scheduling with a small number of machines, Online knapsack with removal and recourse, An efficient algorithm for semi-online multiprocessor scheduling with given total processing time, Online bin stretching with three bins, Unnamed Item, Semi-online scheduling revisited, The online knapsack problem: advice and randomization, Optimal algorithms for online scheduling with bounded rearrangement at the end, Semi-online scheduling with machine cost., Online scheduling with reassignment, ONLINE AND SEMI-ONLINE SCHEDULING ON CAPACITATED TWO-PARALLEL MACHINES, Exploiting incomplete information to manage multiprocessor tasks with variable arrival rates, Online scheduling with rejection and reordering: exact algorithms for unit size jobs, Semi-online scheduling with ``end of sequence information, Semi-online scheduling on two uniform machines with the known largest size, Two uniform machines with nearly equal speeds: unified approach to known sum and known optimum in semi on-line scheduling, Scheduling In the random-order model, Semi-online Machine Covering on Two Hierarchical Machines with Known Total Size of Low-Hierarchy Jobs, Online Makespan Scheduling with Job Migration on Uniform Machines, Online bin stretching with bunch techniques, Optimal semi-online algorithms for preemptive scheduling problems with inexact partial information, A better semi-online algorithm for \(\mathrm Q3/s_{1} = s_{2}\leq s_{3}/C_{\mathrm{min}}\) with the known largest size, List scheduling for jobs with arbitrary release times and similar lengths, Online algorithms with advice: the tape model, Semi-online scheduling with decreasing job sizes, Online scheduling for jobs with nondecreasing release times and similar lengths on parallel machines, Semi-online scheduling on two uniform processors, Semi-on-line scheduling problems for maximizing the minimum machine completion time, Semi-online preemptive scheduling: one algorithm for all variants, Machine covering with combined partial information, Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data, Semi-online scheduling with known partial information about job sizes on two identical machines, Semi-on-line multiprocessor scheduling with given total processing time, Optimal semi-online preemptive algorithms for machine covering on two uniform machines, Online scheduling with a buffer on related machines, Semi-on-line scheduling with ordinal data on two uniform machines, Preemptive online algorithms for scheduling with machine cost, Several semi-online scheduling problems on two identical machines with combined information, Randomized on-line scheduling similar jobs to minimize makespan on two identical processors, On-line bin-stretching, Preemptive semi-online algorithms for parallel machine scheduling with known total size, Dynamic programming optimization in line of sight networks, Two semi-online scheduling problems on two uniform machines, An improved parametric algorithm on two-machine scheduling with given lower and upper bounds for the total processing time, Extension of algorithm list scheduling for a semi-online scheduling problem, OPTIMAL PREEMPTIVE SEMI-ONLINE ALGORITHM FOR SCHEDULING TIGHTLY-GROUPED JOBS ON TWO UNIFORM MACHINES, Dividing a Territory Among Several Vehicles, Online scheduling on two uniform machines to minimize the makespan, Online makespan scheduling with job migration on uniform machines, Tight lower bounds for semi-online scheduling on two uniform machines with known optimum, A 2-competitive largest job on least loaded machine online algorithm based on the multi list scheduling model, Semi-online scheduling jobs with tightly-grouped processing times on three identical machines, Online hierarchical scheduling on two machines with known total size of low-hierarchy jobs, Discovering and certifying lower bounds for the online bin stretching problem, Ordinal algorithms for parallel machine scheduling with nonsimultaneous machine available times, Semi-on-line problems on two identical machines with combined partial information

Cites Work