An Application of Bin-Packing to Multiprocessor Scheduling

DOI10.1137/0207001zbMath0374.68032OpenAlexW2019133545MaRDI QIDQ4151721

Michael R. Garey, Edward G. jun. Coffman, David S. Johnson

Publication date: 1978

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

Full work available at URL: https://semanticscholar.org/paper/33627d1d96c6031f65c38582d7c791c3891e83c5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Deterministic scheduling theory in operations research (90B35) Algorithms in computer science (68W99)

Related Items

Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem, Parallel machine scheduling under a grade of service provision, A note on longest processing time algorithms for the two uniform parallel machine makespan minimization problem, A characterization of optimal multiprocessor schedules and new dominance rules, An analysis of lower bound procedures for the bin packing problem, A robust strategy approach to a strategic mobility problem, A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes, List scheduling algorithms to minimize the makespan on identical parallel machines, On the worst-case ratio of a compound multiprocessor scheduling algorithm, New approximation bounds for LPT scheduling, An introduction to stochastic bin packing-based server consolidation with conflicts, Scheduling with flexible resources in parallel workcenters to minimize maximum completion time, Linear time algorithms for parallel machine scheduling, Energy-oriented scheduling based on evolutionary algorithms, Worst-case performance analysis of some approximation algorithms for minimizing makespan and flowtime, Scheduling a single parallel-batching machine with non-identical job sizes and incompatible job families, Multiprocessor scheduling: Combining LPT and MULTIFIT, Approximate algorithms for the \(P\parallel C_{\max}\) problem, Performance ratios of the Karmarkar-Karp differencing method, Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations, Exact and heuristic algorithms for thrift cyclic scheduling, A variable neighborhood search algorithm for human resource selection and optimization problem in the home appliance manufacturing industry, The longest processing time rule for identical parallel machines revisited, Scheduling web advertisements: a note on the minspace problem, Heuristic stability: a permutation disarray measure, Nature inspired genetic algorithms for hard packing problems, Bin packing: Maximizing the number of pieces packed, On the weak computability of a four dimensional orthogonal packing and time scheduling problem, Dynamic fleet scheduling with uncertain demand and customer flexibility, Multiprofessor scheduling, Partial solutions and multifit algorithm for multiprocessor scheduling, A hybrid placement strategy for the three-dimensional strip packing problem, Scheduling and fixed-parameter tractability, A note on posterior tight worst-case bounds for longest processing time schedules, 1-optimality of static BSP computations: Scheduling independent chains as a case study., A tight linear time \(\frac{13}{12}\)-approximation algorithm for the \(P2 || C_{\max}\) problem, Scheduling on same-speed processors with at most one downtime on each machine, Approximation for scheduling on uniform nonsimultaneous parallel machines, Identical parallel machine scheduling with time-dependent processing times, Computer-assisted proof of performance ratios for the differencing method, An exact algorithm for the identical parallel machine scheduling problem., Exact performance of MULTIFIT for nonsimultaneous machines, Scheduling batches on parallel machines with major and minor set-ups, A state-of-the-art review of parallel-machine scheduling research, Less is more: variable neighborhood search for integrated production and assembly in smart manufacturing, On the exact upper bound for the Multifit processor scheduling algorithm, Improved 0/1-interchange scheduling, Approximability of scheduling with fixed jobs, A dynamic edge covering and scheduling problem: complexity results and approximation algorithms, Minimizing the makespan on two identical parallel machines with mold constraints, Minimizing the makespan in nonpreemptive parallel machine scheduling problem, A hybrid DBH-VNS for high-end equipment production scheduling with machine failures and preventive maintenance activities, Scheduling semiconductor multihead testers using metaheuristic techniques embedded with lot-specific and configuration-specific information, Tighter bound for MULTIFIT scheduling on uniform processors, Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time, Unrelated parallel machine scheduling -- perspectives and progress, Multi-machine scheduling with deteriorating jobs and scheduled maintenance, Scheduling on uniform processors with at most one downtime on each machine, Bee colony optimization for scheduling independent tasks to identical processors, A simple proof of the inequality \(\text{FFD}(L)\leq {11 \over 9} \text{OPT}(L)+1\), \(\forall L\) for the FFD bin-packing algorithm, Scheduling identical parallel machines with tooling constraints, Cutting stock problems with nondeterministic item lengths: a new approach to server consolidation, A cutting plane approach for integrated planning and scheduling, An efficient deterministic heuristic for two-dimensional rectangular packing, A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria, A simple proof of the inequality \(R_ M(MF(k)) \leq 1.2 + (1/2^ k)\) in multiprocessor scheduling, A composite algorithm for multiprocessor scheduling, Scheduling jobs under increasing linear machine maintenance time, The effect of machine availability on the worst-case performance of LPT, Set-based broadcast scheduling for minimizing the worst access time of multiple data items in wireless environments, Scheduling algorithms for flexible flowshops: Worst and average case performance, Bin packing problem with conflicts and item fragmentation, Performance of the LPT algorithm in multiprocessor scheduling, Improved approximation algorithms for two-stage flowshops scheduling problem, Minimizing the number of tardy jobs in the flowshop problem with operation and resource flexibility, Scalable optimal deployment in the cloud of component-based applications using optimization modulo theory, mathematical programming and symmetry breaking, Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint, The multifit algorithm for set partitioning containing kernels, Optimal and heuristic solution methods for a multiprocessor machine scheduling problem, Parallel bundle-based decomposition for large-scale structured mathematical programming problems, Parallel machines scheduling with nonsimultaneous machine available time, A note on MULTIFIT scheduling for uniform machines, Tighter approximation bounds for LPT scheduling in two special cases, Maximizing the production rate in simple assembly line balancing -- A branch and bound procedure, Bin packing with restricted piece sizes, A typology of cutting and packing problems, Bin packing and multiprocessor scheduling problems with side constraint on job types, Minimizing makespan subject to minimum total flow-time on identical parallel machines, The \(k\)-partitioning problem, A cutting plane algorithm for the unrelated parallel machine scheduling problem, Packing-based branch-and-bound for discrete malleable task scheduling, Tight approximation bounds for the LPT rule applied to identical parallel machines with small jobs, The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines, The multiple traveling salesman problem in presence of drone- and robot-supported packet stations, A tighter bound for FFd algorithm, Performance of scheduling algorithms for no-wait flowshops with parallel machines, First fit decreasing scheduling on uniform multiprocessors, Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm, A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective, Analytical loading models in flexible manufacturing systems, List-scheduling and column-generations for scheduling of n job-groups with set up time and due date through m identical parallel machines to minimize makespan, A Packing Problem You Can Almost Solve by Sitting on Your Suitcase, Scheduling manufacturing systems for delayed product differentiation in agile manufacturing, Machine scheduling performance with maintenance and failure, Parallel machine scheduling with nested processing set restrictions, State-Variable Modeling for a Class of Two-Stage Stochastic Optimization Problems, Mathematical models and approximate solution approaches for the stochastic bin packing problem, Exact algorithms for solving the constrained parallel-machine scheduling problems with divisible processing times and penalties, Worst-case analysis of LPT scheduling on a small number of non-identical processors, The constrained parallel-machine scheduling problem with divisible processing times and penalties, Priority-based bin packing with subset constraints, Performance of Heuristics for a Computer Resource Allocation Problem, Unnamed Item, Competitive strategies of U.S. presidential candidates in election campaigns, A hierarchical approach for metal parts fabrication, Minimizing labor requirements in a periodic vehicle loading problem, Minimizing makespan subject to minimum flowtime on two identical parallel machines, Scheduling with product family set-up times: an application in TFT LCD manufacturing, A linear time approximation algorithm for multiprocessor scheduling, Scheduling advertisements on a web page to maximize revenue, A hybrid two-stage flexible flowshop scheduling problem with m identical parallel machines and a burn-in processor separately, On scheduling parallel machines with two setup classes, Heuristic scheduling of parallel machines with sequence-dependent set-up times, Branch and Price for Chance-Constrained Bin Packing, NP-Complete operations research problems and approximation algorithms, Unnamed Item, Approximation scheduling algorithms: a survey, Analysis of partial setup strategies for solving the operational planning problem in parallel machine electronic assembly systems, Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System, Adaptive Bin Packing with Overflow