A state-of-the-art review of parallel-machine scheduling research

DOI10.1016/0377-2217(90)90215-WzbMath0707.90053OpenAlexW2071277483MaRDI QIDQ919994

C. C. S. Sin, Cheng, T. C. Edwin

Publication date: 1990

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(90)90215-w

zbMATH Keywords

surveyclassificationsequencingdeterministic parallel-machine scheduling

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02)

Related Items (only showing first 100 items - show all)

Hybrid meta-heuristics for minimizing the total weighted completion time on uniform parallel machines ⋮ Parallel machines scheduling with machine preference via agent-based approach ⋮ A state-space search approach for parallel processor scheduling problems with arbitrary precedence relations ⋮ Distributed scheduling: a review of concepts and applications ⋮ Parallel machine scheduling with preference of machines ⋮ Minimising makespan on parallel machines with precedence constraints and machine eligibility restrictions ⋮ Balancing perfectly periodic service schedules: An application from recycling and waste management ⋮ Minimizing makespan in hybrid flowshops ⋮ Job scheduling of diffusion furnaces in semiconductor fabrication facilities ⋮ Branch-and-price approach for robust parallel machine scheduling with sequence-dependent setup times ⋮ Scheduling manufacturing systems for delayed product differentiation in agile manufacturing ⋮ Modeling the parallel machine scheduling problem with step deteriorating jobs ⋮ Mass customization in videotape duplication and conversion: challenges of flexible duplication systems, fast delivery, and electronic service ⋮ A novel timetabling algorithm for a furnace process for semiconductor fabrication with constrained waiting and frequency-based setups ⋮ Minimizing resource consumption on uniform parallel machines with a bound on makespan ⋮ Optimisation of fault-tolerant fabric-cutting schedules using genetic algorithms and fuzzy set theory ⋮ Minimizing total tardiness and earliness on unrelated parallel machines with controllable processing times ⋮ ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times ⋮ Energy-oriented scheduling based on evolutionary algorithms ⋮ Scheduling with job-splitting considering learning and the vital-few law ⋮ BISON: A fast hybrid procedure for exactly solving the one-dimensional bin packing problem ⋮ Acquisition planning and scheduling of computing resources ⋮ Reducing ergonomic risks by job rotation scheduling ⋮ Approximate algorithms for the \(P\parallel C_{\max}\) problem ⋮ An exact extended formulation for the unrelated parallel machine total weighted completion time problem ⋮ Using \(\ell^p\)-norms for fairness in combinatorial optimisation ⋮ Minimizing the number of tardy jobs for \(m\) parallel machines ⋮ Scheduling unrelated parallel machines with sequence-dependent setups ⋮ Scheduling jobs within time windows on identical parallel machines: New model and algorithms ⋮ The berth allocation problem with mobile quay walls: problem definition, solution procedures, and extensions ⋮ Unrelated parallel machine scheduling problem with special controllable processing times and setups ⋮ Two parallel-machine scheduling problems with function constraint ⋮ Partial solutions and multifit algorithm for multiprocessor scheduling ⋮ An ILS heuristic for the ship scheduling problem: application in the oil industry ⋮ A note on posterior tight worst-case bounds for longest processing time schedules ⋮ A hybrid multi-objective evolutionary algorithm approach for handling sequence- and machine-dependent set-up times in unrelated parallel machine scheduling problem ⋮ A mixed integer formulation and an efficient metaheuristic for the unrelated parallel machine scheduling problem: total tardiness minimization ⋮ Scheduling Unrelated Parallel Machines with Sequence Dependent Setup Times and Weighted Earliness–Tardiness Minimization ⋮ The balanced maximally diverse grouping problem with integer attribute values ⋮ Literal Selection in Switching Lattice Design ⋮ GRASP with path-relinking for the non-identical parallel machine scheduling problem with minimising total weighted completion times ⋮ Improving fleet utilization for carriers by interval scheduling ⋮ A robust optimization approach for the unrelated parallel machine scheduling problem ⋮ Unnamed Item ⋮ Parallel machine scheduling of machine-dependent jobs with unit-length. ⋮ Minimizing the makespan in nonpreemptive parallel machine scheduling problem ⋮ Using high performance computing for unrelated parallel machine scheduling with sequence-dependent setup times: development and computational evaluation of a parallel branch-and-price algorithm ⋮ An enhanced formulation and simple heuristic for scheduling jobs on unrelated parallel machines ⋮ Scheduling problems in master-slave model ⋮ A capacitated lot-sizing model with sequence-dependent setups, parallel machines and bi-part injection moulding ⋮ A lexi-search algorithm for a time minimizing assignment problem. ⋮ Minimization of makespan in generalized assignment problem. ⋮ Distributionally robust scheduling on parallel machines under moment uncertainty ⋮ A POSTERIOR COMPETITIVENESS FOR LIST SCHEDULING ALGORITHM ON MACHINES WITH ELIGIBILITY CONSTRAINTS ⋮ Capacitated lot sizing and scheduling with parallel machines and shared buffers: A case study in a packaging company ⋮ Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms ⋮ Scheduling rules to minimize total tardiness in a parallel machine problem with setup and calendar constraints ⋮ A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria ⋮ Scheduling unrelated parallel machines with optional machines and jobs selection ⋮ A PC-based production scheduling system using a mixed integer programming approach ⋮ A composite algorithm for multiprocessor scheduling ⋮ Uniform parallel machine scheduling with resource consumption constraint ⋮ Assembly line balancing and group working: a heuristic procedure for workers' groups operating on the same product and workstation ⋮ A graph-oriented approach for the minimization of the number of late jobs for the parallel machines scheduling problem ⋮ Scheduling experiments on a nulear reactor using mixed integer programming ⋮ Scheduling uniform parallel dedicated machines with job splitting, sequence-dependent setup times, and multiple servers ⋮ Parallel machine scheduling with precedence constraints and setup times ⋮ Scheduling of unrelated parallel manufacturing cells with limited human resources ⋮ Iterated greedy local search methods for unrelated parallel machine scheduling ⋮ Analysis of the similarities and differences of job-based scheduling problems ⋮ Parallel machine scheduling with tool loading ⋮ Machine scheduling in production: a content analysis ⋮ Optimal solutions for a dock assignment problem with trailer transportation ⋮ A Multiobjective Optimization Approach to Solve a Parallel Machines Scheduling Problem ⋮ Optimal and heuristic solution methods for a multiprocessor machine scheduling problem ⋮ Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs ⋮ Logic-based Benders decomposition method for the \textit{seru} scheduling problem with sequence-dependent setup time and DeJong's learning effect ⋮ Minimizing the schedule length for a parallel 3D-grid precedence graph ⋮ A new model and algorithm for uncertain random parallel machine scheduling problem ⋮ Parallel machine scheduling with splitting jobs ⋮ Heuristics for unrelated machine scheduling with precedence constraints ⋮ Scheduling under a common due-date on parallel unrelated machines ⋮ Multistage hybrid flowshop scheduling with identical jobs and uniform parallel machines ⋮ A study of integer programming formulations for scheduling problems ⋮ A cutting plane algorithm for the unrelated parallel machine scheduling problem ⋮ Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions ⋮ A variant of time minimizing assignment problem ⋮ Flowshop scheduling with identical jobs and uniform parallel machines ⋮ Determination of fault-tolerant fabric-cutting schedules in a just-in-time apparel manufacturing environment ⋮ The multiple traveling salesman problem in presence of drone- and robot-supported packet stations ⋮ Analysis of partial setup strategies for solving the operational planning problem in parallel machine electronic assembly systems ⋮ Scheduling hybrid flowshops to minimize maximum tardiness or maximum completion time ⋮ Product grouping for batch processes ⋮ A survey of the state-of-the-art of common due date assignment and scheduling research ⋮ Unrelated parallel machine scheduling with multiple time windows: an application to Earth observation satellite scheduling ⋮ Parallel machine scheduling to minimize costs for earliness and number of tardy jobs ⋮ Optimal multiprocessor task scheduling using dominance and equivalence relations ⋮ A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective ⋮ Parallel machine scheduling with additional resources: notation, classification, models and solution methods ⋮ Bi-Objective Flow Shop Scheduling with Equipotential Parallel Machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• New directions in scheduling theory
• On the NP-completeness of the n/m/parallel/\(\sum_{i\leq i\leq m}\{\sum w_ j\sum t_ j\}\) scheduling problem
• Probabilistic bounds for dual bin-packing
• The rate of convergence to optimality of the LPT rule
• New trends in machine scheduling
• Solving a bicriterion scheduling problem
• A bicriterion approach to time/cost trade-offs in sequencing
• NP-complete scheduling problems
• Optimal scheduling for two-processor systems
• Scheduling with Deadlines and Loss Functions
• A linear time approximation algorithm for multiprocessor scheduling
• Combinatorial Analysis of an Efficient Algorithm for Processor and Storage Allocation
• A Note on Expected Makespans for Largest-First Sequences of Independent Tasks on Two Processors
• Tighter Bounds for the Multifit Processor Scheduling Algorithm
• Tight Bounds and Probabilistic Analysis of Two Heuristics for Parallel Processor Scheduling
• Hu's precedence tree scheduling algorithm: A simple proof
• Scheduling Independent Tasks on Uniform Processors
• A Heuristic for Common Due-date Assignment and Job Scheduling on Parallel Machines
• Bounds for Multifit Scheduling on Uniform Processors
• On the Expected Relative Performance of List Scheduling
• The Asymptotic Optimality of the LPT Rule
• Parallel Machine Scheduling: Processing Rates Dependent on Number of Jobs in Operation
• Note—A Branch-and-Bound Approach to the Bicriterion Scheduling Problem Involving Total Flowtime and Range of Lateness
• An improved branching scheme for the branch and bound procedure of schedulingnjobs onmparallel machines to minimize total weighted flowtime
• Preemptive Scheduling with Due Dates
• A New Algorithm for Preemptive Scheduling of Trees
• Bounds on Schedules for Independent Tasks with Similar Execution Times
• Nonpreemptive LP-Scheduling on Homogeneous Multiprocessor Systems
• Evaluation of a Heuristic for Scheduling Independent Jobs on Parallel Identical Processors
• On Scheduling Independent Tasks with Restricted Execution Times
• Linear-Time Algorithms for Scheduling on Parallel Processors
• An Almost-Linear Algorithm for Two-Processor Scheduling
• Scheduling to Maximize the Minimum Processor Finish Time in a Multiprocessor System
• Efficiency of a Good But Not Linear Set Union Algorithm
• On the Computational Complexity of Combinatorial Problems
• Algorithms for Scheduling Independent Tasks
• Analysis of Several Task-Scheduling Algorithms for a Model of Multiprogramming Computer Systems
• On Two—Processor Scheduling of One— or Two—Unit Time Tasks with Precedence Constraints
• Scheduling Tasks with Nonuniform Deadlines on Two Processors
• A Level Algorithm for Preemptive Scheduling
• On general routing problems
• A Survey of Scheduling Rules
• A parallel sequencing algorithm for minimizing total cost
• An Application of Bin-Packing to Multiprocessor Scheduling
• Worst Case Analysis of Two Scheduling Algorithms
• On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming
• Scheduling Equal-Length Tasks Under Treelike Precedence Constraints to Minimize Maximum Lateness
• On the Complexity of Mean Flow Time Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Some simple scheduling algorithms
• Scheduling Opposing Forests
• Scheduling independent tasks to reduce mean finishing time
• An Almost-Optimal Algorithm for the Assembly Line Scheduling Problem
• Scheduling with parallel processors and linear delay costs
• Scheduling with Deadlines and Loss Functions on k Parallel Machines
• Bounds for Certain Multiprocessing Anomalies
• Optimal Preemptive Scheduling on Two-Processor Systems
• A Functional Equation and its Application to Resource Allocation and Sequencing Problems
• Bounds on Multiprocessing Timing Anomalies
• Optimal Sequencing of Two Equivalent Processors
• Erratum “Optimal Sequencing of Two Equivalent Processors”
• The complexity of theorem-proving procedures
• Technical Note—Minimizing Average Flow Time with Parallel Machines

This page was built for publication: A state-of-the-art review of parallel-machine scheduling research