Parallel machine scheduling with precedence constraints and setup times

This paper presents different methods for solving parallel machine scheduling problems with precedence constraints and setup times between the jobs. These problems are strongly NP-hard and it is even conjectured that no list scheduling algorithm can be defined without explicitly considering jointly scheduling and resource allocation. We propose dominance conditions based on the analysis of the problem structure and an extension to setup times of the energetic reasoning constraint propagation algorithm. An exact branch-and-bound procedure and a climbing discrepancy search (CDS) heuristic based on these components are defined. We show how the proposed dominance rules can still be valid in the CDS scheme. The proposed methods are evaluated on a set of randomly generated instances and compared with previous results from the literature and those obtained with an efficient commercial solver. We conclude that our propositions are quite competitive and our results even outperform other approaches in most cases.

• Publication year

  2009

• Venue

  Computers & Operations Research

• Publication date

  2009-02-18

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/j.cor.2010.03.003arXiv 0902.3121
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• IBM ILOG CP Optimizer for Detailed Scheduling Illustrated on Three Problems

  2009cited by this paper
• Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times

  2008cited by this paper
• Search tree based approaches for parallel machine scheduling

  2008influential reference
• Scheduling Integrated Circuit Assembly Operations on Die Bonder

  2007cited by this paper
• An exact method for Pm/sds, ri/sum(i=1, n, Ci) problem

  2007cited by this paper
• YIELDS: A Yet Improved Limited Discrepancy Search for CSPs

  2007cited by this paper
• Self-Adapting Large Neighborhood Search: Application to Single-Mode Scheduling Problems

  2007cited by this paper
• Climbing depth-bounded discrepancy search for solving hybrid flow shop problems

  2007cited by this paper
• Schedule Generation Schemes for the Job-Shop Problem with Sequence-Dependent Setup Times: Dominance Properties and Computational Analysis

  2005cited by this paper
• Parallel machine scheduling through column generation: minimax objective functions, release dates, deadlines and/or generalized precedence constraints

  2005cited by this paper
• Earliness-tardiness scheduling with setup considerations

  2005cited by this paper
• RanGen: A Random Network Generator for Activity-on-the-Node Networks

  2003cited by this paper
• Project Scheduling with Time Windows and Scarce Resources

  2003influential reference
• An Experimental Study of Algorithms for Weighted Completion Time Scheduling

  2002influential reference
• List scheduling in a parallel machine environment with precedence constraints and setup times

  2001influential reference
• Discrepancy-Bounded Depth First Search

  2000cited by this paper
• A BRANCH-AND-BOUND ALGORITHM FOR PARALLEL MACHINE SCHEDULING PROBLEMS

  2000cited by this paper
• Solving Parallel Machine Scheduling Problems by Column Generation

  1999cited by this paper
• Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems

  1998cited by this paper
• Variable neighborhood search: Principles and applications

  1998cited by this paper
• New Benchmark Results for the Resource-Constrained Project Scheduling Problem

  1997influential reference
• Depth-bounded Discrepancy Search

  1997influential reference
• List scheduling revisited

  1996cited by this paper
• Parallel machine scheduling with release dates, due dates and family setup times

  1996cited by this paper
• Improved Limited Discrepancy Search

  1996cited by this paper
• CONSISTENCY ENFORCING IN SCHEDULING: A GENERAL FORMULATION BASED ON ENERGETIC REASONING

  1996cited by this paper
• Rolling horizon procedures for dynamic parallel machine scheduling with sequence-dependent setup times.

  1995cited by this paper
• Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem

  1995cited by this paper
• Limited Discrepancy Search

  1995influential reference
• A state-of-the-art review of parallel-machine scheduling research

  1990cited by this paper
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey

  1977influential reference

• Mathematical models and an effective exact algorithm for unrelated parallel machine scheduling with family setup times and machine cost

  2024cites this paper
• Exploring the evolution of machine scheduling through a computational approach

  2024cites this paper
• Hybrid multi-objective evolutionary meta-heuristics for a parallel machine scheduling problem with setup times and preferences

  2023cites this paper
• A Resilient and Effective Task Scheduling Approach for Industrial Human-Robot Collaboration

  2022cites this paper
• Reducing response latency of composite functions-as-a-service through scheduling

  2022cites this paper
• Decomposition approaches for parallel machine scheduling of step-deteriorating jobs to minimize total tardiness and energy consumption

  2021cites this paper
• A two-stage solution approach for plastic injection machines scheduling problem

  2021cites this paper
• Scheduling uniform parallel dedicated machines with job splitting, sequence-dependent setup times, and multiple servers

  2021cites this paper
• Constraint programming approach for multi-resource-constrained unrelated parallel machine scheduling problem with sequence-dependent setup times

  2021cites this paper
• Introducing preferences in scheduling applications

  2021cites this paper
• A decomposition solution approach to the troops-to-tasks assignment in military peacekeeping operations

  2020cites this paper
• HEART: Unrelated parallel machines problem with precedence constraints for task scheduling in cloud computing using heuristic and meta‐heuristic algorithms

  2020cites this paper
• Scheduling Methods to Reduce Response Latency of Function as a Service

  2020cites this paper
• Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network

  2020cites this paper
• DSS approach for heterogeneous parallel machines scheduling considering proximate supply chain constraints

  2020cites this paper
• A hybrid metaheuristic algorithm for a parallel machine scheduling problem with dependent setup times

  2019cites this paper
• A metaheuristic algorithm and simulation to study the effect of learning or tiredness on sequence-dependent setup times in a parallel machine scheduling problem

  2019cites this paper
• Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network

  2019cites this paper
• Minimizing the total completion time in scheduling problems with sequence dependent setup times

  2019cites this paper
• Problèmes d'ordonnancement et de moyens de transport des systèmes de production: prise en compte de la qualité de service. (Scheduling and routing problems in production systems: taking quality of service into consideration)

  2019cites this paper
• A DSS approach for heterogeneous parallel machines scheduling with due windows, processor-&-sequence-dependent setup and proximate supply chain constraints

  2019cites this paper
• 3D Printer Scheduling for Shortest Time Production of Weapon Parts

  2019cites this paper
• TESE DE DOUTORADO No 285 SCHEDULING MANEUVERS FOR THE RESTORATION OF ELECTRIC POWER DISTRIBUTION NETWORKS

  2018cites this paper
• On the m-clique free interval subgraphs polytope: polyhedral analysis and applications

  2018cites this paper
• On the m-clique free interval subgraphs polytope: polyhedral analysis and applications

  2018cites this paper
• MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints

  2018cites this paper
• Metaheuristics for the selection and scheduling of jobs with time-dependent durations

  2017cites this paper
• User's priority focused resource provisioning over cloud computing infrastructure

  2017cites this paper
• A realistic variant of bi-objective unrelated parallel machine scheduling problem: NSGA-II and MOACO approaches

  2017cites this paper
• A Constraint Programming Approach to Optimize Network Calls by Minimizing Variance in Data Availability Times

  2017cites this paper
• Mixed integer formulations for the multiple minimum latency problem

  2017cites this paper
• A Mix Integer Programming Model for Parallel Machine Scheduling Problem : Using Shared Resource

  2017cites this paper
• An exact dynamic programming algorithm for the precedence-constrained class sequencing problem

  2017cites this paper
• Fen Bilimleri Dergisi

  2017cites this paper
• Metaheuristics for a job scheduling problem with smoothing costs relevant for the car industry

  2016cites this paper
• Design of high-performing hybrid meta-heuristics for unrelated parallel machine scheduling with machine eligibility and precedence constraints

  2016cites this paper
• An effective estimation of distribution algorithm for solving uniform parallel machine scheduling problem with precedence constraints

  2016influential citation
• Optimizing network calls by minimizing variance in data availability times

  2016cites this paper
• Unrelated Parallel Machine Scheduling Problem with Precedence Constraints: Polyhedral Analysis and Branch-and-Cut

  2016cites this paper
• Time-dependent formulations for minimizing total completion time in a parallel machine scheduling problem with dependent setup times

  2016cites this paper
• Parallel Scheduling in the Cloud Systems : Approximate and Exact Methods

  2016cites this paper
• Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions

  2016cites this paper
• The Integration of Decision Analysis Techniques in High-Throughput Clinical Analyzers

  2016cites this paper
• Solving the job shop scheduling problem with operators by depth-first heuristic search enhanced with global pruning rules

  2015cites this paper
• Practical solutions for a dock assignment problem with trailer transportation

  2015cites this paper
• SEQUENCIAMENTO DE TAREFAS EM M ´AQUINAS PARALELAS COM TEMPOS DE PREPARAC¸ ˜AO E PRECED ˆENCIA ENTRE AS TAREFAS: MODELAGEM E HEUR´ISTICAS CONSTRUTIVAS

  2015cites this paper
• From packing to dispatching: supply chain optimization techniques

  2015cites this paper
• Reheat furnace scheduling with energy consideration

  2015cites this paper
• The third comprehensive survey on scheduling problems with setup times/costs

  2015cites this paper
• A Linear Programming Approach for Parallel Cell Scheduling with Sequence-Dependent Setup Times

  2014cites this paper
• Dynamic Pareto-optimal group scheduling in parallel machine shop

  2014cites this paper
• A GRASP approach to transporter scheduling for ship assembly block operations management

  2013cites this paper
• An efficient hybrid search algorithm for job shop scheduling with operators

  2013cites this paper
• A Hybrid Genetic Algorithm to Minimize Total Tardiness for Unrelated Parallel Machine Scheduling with Precedence Constraints

  2013cites this paper
• Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm

  2013cites this paper
• Combining Global Pruning Rules with Depth-First Search for the Job Shop Scheduling Problem with Operators

  2012cites this paper
• Programação de tarefas em máquinas paralelas não-relacionadas com tempos de setup dependentes da sequência

  2012cites this paper
• List Scheduling Algorithm for Static Task with Precedence Constraints for Cyber-physical Systems

  2012cites this paper
• A GRASP approach to transporter scheduling and routing at a shipyard

  2012cites this paper
• Lot Sizing and Scheduling in Parallel Uniform Machines – A Case Study

  2012cites this paper
• Weight-based Heuristics for Constraint Satisfaction and Combinatorial Optimization Problems

  2012cites this paper
• An efficient hybrid evolutionary algorithm for scheduling with setup times and weighted tardiness minimization

  2012cites this paper
• Scheduler-oriented algorithms to improve human-machine cooperation in transportation scheduling support systems

  2012cites this paper
• Scalable Scheduling for Hardware-Accelerated Functional Verification

  2011cites this paper
• Discrepancy search for the flexible job shop scheduling problem

  2010cites this paper
• An hybrid CP/MILP method for scheduling with energy costs

  2010cites this paper
• Une approche interdisciplinaire pour l'ordonnancement des transports

  2010cites this paper