Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
From MaRDI portal
Publication:3980518
DOI10.1287/opre.39.4.648zbMath0736.90043OpenAlexW2107481047WikidataQ60307347 ScholiaQ60307347MaRDI QIDQ3980518
Publication date: 26 June 1992
Published in: Operations Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1287/opre.39.4.648
Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
Families of non-IRUP instances of the one-dimensional cutting stock problem, Single machine scheduling with two competing agents, arbitrary release dates and unit processing times, Scheduling High Multiplicity Jobs on Parallel Multi-Purpose Machines with Setup Times and Machine Available Times, Optimal packet-to-slot assignment in mobile telecommunications, Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions, Scheduling with safety distances, An alternative approach for proving the NP-hardness of optimization problems, A note on the complexity of the problem of two-agent scheduling on a single machine, The assignment problem with nearly Monge arrays and incompatible partner indices, High-multiplicity scheduling on one machine with forbidden start and completion times, An algorithm for the detection and construction of Monge sequences, A fluid approach to large volume job shop scheduling, Heuristics for the integer one-dimensional cutting stock problem: A computational study, Polynomial algorithms for a two-class multiprocessor scheduling problem in mobile telecommunications systems, Parameterized complexity of configuration integer programs, High-multiplicity \(N\)-fold IP via configuration LP, Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming, The maximum deviation just-in-time scheduling problem., Many Visits TSP Revisited, Using quadratic programming to solve high multiplicity scheduling problems on parallel machines, A polynomial algorithm for an integer quadratic non-separable transportation problem, Packet scheduling in third-generation mobile systems with UTRA-TDD air interface, Batch scheduling in a two-level supply chain -- a focus on the supplier, On the high multiplicity traveling salesman problem, Scheduling jobshops with some identical or similar jobs, Scheduling with periodic availability constraints and irregular cost functions, The complexity of CO-agent scheduling to minimize the total completion time and total number of tardy jobs, A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times, Scheduling a proportionate flow shop of batching machines, Many-visits TSP revisited, Cyclic lot-sizing problems with sequencing costs, Feasibility criteria for high-multiplicity partitioning problems, New complexity and approximability results for minimizing the total weighted completion time on a single machine subject to non-renewable resource constraints, Exact and approximate algorithms for high-multiplicity parallel machine scheduling, Low-complexity algorithms for sequencing jobs with a fixed number of job-classes, A framework for the complexity of high-multiplicity scheduling problems, An asymptotically exact algorithm for the high-multiplicity bin packing problem, A polynomial algorithm for lot-size scheduling of two type tasks.
