Parallel machine scheduling with precedence constraints and setup times
From MaRDI portal
Publication:991370
DOI10.1016/J.COR.2010.03.003zbMATH Open1231.90192arXiv0902.3121OpenAlexW2009835506MaRDI QIDQ991370FDOQ991370
Authors: Bernat Gacias, Christian Artigues, Pierre Lopez 
Publication date: 7 September 2010
Published in: Computers \& Operations Research (Search for Journal in Brave)
Abstract: This paper presents different methods for solving parallel machine scheduling problems with precedence constraints and setup times between the jobs. Limited discrepancy search methods mixed with local search principles, dominance conditions and specific lower bounds are proposed. 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.
Full work available at URL: https://arxiv.org/abs/0902.3121
Recommendations
- List scheduling in a parallel machine environment with precedence constraints and setup times
- Scheduling preemptive jobs with precedence constraints on parallel machines
- A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times
- An exact method for \(Pm/sds, r_{i}/ \sum^{n}_{i=1} C_{i}\) problem
- Analysis of Heuristics for Preemptive Parallel Machine Scheduling with Batch Setup Times
local searchbranch-and-boundsetup timesparallel machine schedulingprecedence constraintsdominance conditionslimited discrepancy search
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic scheduling theory in operations research (90B35)
Cites Work
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Variable neighborhood search: Principles and applications
- A state-of-the-art review of parallel-machine scheduling research
- Semi-active, active, and non-delay schedules for the resource-constrained project scheduling problem
- List scheduling in a parallel machine environment with precedence constraints and setup times
- Rangen: A random network generator for activity-on-the-node networks
- Title not available (Why is that?)
- New Benchmark Results for the Resource-Constrained Project Scheduling Problem
- Solving Parallel Machine Scheduling Problems by Column Generation
- Earliness-tardiness scheduling with setup considerations
- Rolling horizon procedures for dynamic parallel machine scheduling with sequence-dependent setup times
- Heuristics for minimizing maximum lateness on a single machine with family-dependent set-up times
- Search tree based approaches for parallel machine scheduling
- List scheduling revisited
- Schedule generation schemes for the jop-shop problem with sequence-dependent setup times: dominance properties and computational analysis
- An exact method for \(Pm/sds, r_{i}/ \sum^{n}_{i=1} C_{i}\) problem
- An experimental study of algorithms for weighted completion time scheduling
Cited In (20)
- A two-stage solution approach for plastic injection machines scheduling problem
- Title not available (Why is that?)
- MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints
- Parallel dedicated machines scheduling with chain precedence constraints
- Title not available (Why is that?)
- On the \(m\)-clique free interval subgraphs polytope: polyhedral analysis and applications
- The complexity of parallel machine scheduling of unit-processing-time jobs under level-order precedence constraints
- Scheduling uniform parallel dedicated machines with job splitting, sequence-dependent setup times, and multiple servers
- Practical solutions for a dock assignment problem with trailer transportation
- The third comprehensive survey on scheduling problems with setup times/costs
- List scheduling in a parallel machine environment with precedence constraints and setup times
- Weight-based heuristics for constraint satisfaction and combinatorial optimization problems
- Optimized task scheduling and resource allocation on cloud computing environment using improved differential evolution algorithm
- An exact dynamic programming algorithm for the precedence-constrained class sequencing problem
- Parallel machine scheduling with nested processing set restrictions
- Precedence constrained parallel-machine scheduling of position-dependent jobs
- Discrepancy search for the flexible job shop scheduling problem
- Branch-cut-and-price for scheduling deliveries with time windows in a direct shipping network
- Unrelated parallel machine scheduling problem with precedence constraints: polyhedral analysis and branch-and-cut
- Scheduling rules to minimize total tardiness in a parallel machine problem with setup and calendar constraints
Uses Software
This page was built for publication: Parallel machine scheduling with precedence constraints and setup times
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q991370)
