An Application of Bin-Packing to Multiprocessor Scheduling
From MaRDI portal
Publication:4151721
DOI10.1137/0207001zbMath0374.68032MaRDI QIDQ4151721
David S. Johnson, Edward G. jun. Coffman, Michael R. Garey
Publication date: 1978
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/33627d1d96c6031f65c38582d7c791c3891e83c5
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
90B35: Deterministic scheduling theory in operations research
68W99: Algorithms in computer science
Related Items
Unnamed Item, A hierarchical approach for metal parts fabrication, Heuristic scheduling of parallel machines with sequence-dependent set-up times, Scheduling with product family set-up times: an application in TFT LCD manufacturing, Scheduling manufacturing systems for delayed product differentiation in agile manufacturing, 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 hybrid two-stage flexible flowshop scheduling problem with m identical parallel machines and a burn-in processor separately, Unnamed Item, Minimizing makespan subject to minimum flowtime on two identical parallel machines, Scheduling algorithms for flexible flowshops: Worst and average case performance, Performance of the LPT algorithm in multiprocessor scheduling, Scheduling jobs under increasing linear machine maintenance time, Minimizing the number of tardy jobs in the flowshop problem with operation and resource flexibility, Parallel bundle-based decomposition for large-scale structured mathematical programming problems, Parallel machines scheduling with nonsimultaneous machine available time, Bounds for nonpreemptive scheduling of jobs with similar processing times on multiprocessor systems using the LPT-algorithm, Lower bounds and heuristic algorithms for the \(k_i\)-partitioning problem, Scheduling with flexible resources in parallel workcenters to minimize maximum completion time, Linear time algorithms for parallel machine scheduling, Performance ratios of the Karmarkar-Karp differencing method, Scheduling web advertisements: a note on the minspace problem, Heuristic stability: a permutation disarray measure, Scheduling batches on parallel machines with major and minor set-ups, A state-of-the-art review of parallel-machine scheduling research, On the exact upper bound for the Multifit processor scheduling algorithm, Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time, Heuristics for a two-stage hybrid flowshop scheduling problem with ready times and a product-mix ratio constraint, Optimal and heuristic solution methods for a multiprocessor machine scheduling problem, Tighter approximation bounds for LPT scheduling in two special cases, First fit decreasing scheduling on uniform multiprocessors, On the worst-case ratio of a compound multiprocessor scheduling algorithm, Multiprocessor scheduling: Combining LPT and MULTIFIT, Bin packing: Maximizing the number of pieces packed, Improved 0/1-interchange scheduling, Tighter bound for MULTIFIT scheduling on uniform 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, A simple proof of the inequality \(R_ M(MF(k)) \leq 1.2 + (1/2^ k)\) in multiprocessor scheduling, A note on MULTIFIT scheduling for uniform machines, Maximizing the production rate in simple assembly line balancing -- A branch and bound procedure, The \(k\)-partitioning problem, The worst-case analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines, Performance of scheduling algorithms for no-wait flowshops with parallel machines, A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective, Analytical loading models in flexible manufacturing systems, A robust strategy approach to a strategic mobility problem, List scheduling algorithms to minimize the makespan on identical parallel machines, Approximate algorithms for the \(P\parallel C_{\max}\) problem, 1-optimality of static BSP computations: Scheduling independent chains as a case study., An exact algorithm for the identical parallel machine scheduling problem., Minimizing makespan subject to minimum total flow-time on identical parallel machines, A tighter bound for FFd algorithm, The effect of machine availability on the worst-case performance of LPT, The multifit algorithm for set partitioning containing kernels, 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, A cutting plane algorithm for the unrelated parallel machine scheduling problem, Parallel machine scheduling under a grade of service provision, An analysis of lower bound procedures for the bin packing problem, Approximability of scheduling with fixed jobs, New approximation bounds for LPT scheduling, Multi-machine scheduling with deteriorating jobs and scheduled maintenance, Competitive strategies of U.S. presidential candidates in election campaigns, Minimizing labor requirements in a periodic vehicle loading problem, Scheduling advertisements on a web page to maximize revenue, Machine scheduling performance with maintenance and failure, Parallel machine scheduling with nested processing set restrictions, A linear time approximation algorithm for multiprocessor scheduling, Performance of Heuristics for a Computer Resource Allocation Problem, On scheduling parallel machines with two setup classes, A Packing Problem You Can Almost Solve by Sitting on Your Suitcase, Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System, NP-Complete operations research problems and approximation algorithms, Approximation scheduling algorithms: a survey, Analysis of partial setup strategies for solving the operational planning problem in parallel machine electronic assembly systems
