Mixed integer linear programming and constraint programming models for the online printing shop scheduling problem

DOI10.1016/J.COR.2020.105020MaRDI QIDQ2664355zbMATH OpenOpenAlexWikidataFDO

Authors Willian T. Lunardi, E. G. Birgin, Philippe Laborie, Holger Voos, Débora P. Ronconi

Publication date 20 April 2021

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2006.13064

zbMATH Keywords

constraint programmingmixed integer linear programmingsequence-dependent setup timeflexible job shop scheduling with sequence flexibilityresumable operationsunavailability of the machines

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Deterministic scheduling theory in operations research (90B35) Mixed integer programming (90C11)

Abstract: In this work, the online printing shop scheduling problem is considered. This challenging real problem, that appears in the nowadays printing industry, can be seen as a flexible job shop scheduling problem with sequence flexibility in which precedence constraints among operations of a job are given by an arbitrary directed acyclic graph. In addition, several complicating particularities such as periods of unavailability of the machines, resumable operations, sequence-dependent setup times, partial overlapping among operations with precedence constraints, release times, and fixed operations are also present in the addressed problem. In the present work, mixed integer linear programming and constraint programming models for the minimization of the makespan are presented. Modeling the problem is twofold. On the one hand, the problem is precisely defined. On the other hand, the capabilities and limitations of a commercial software for solving the models are analyzed. Extensive numerical experiments with small-, medium-, and large-sized instances are presented. Numerical experiments show that the commercial solver is able to optimally solve only a fraction of the small-sized instances when considering the mixed integer linear programming model; while all small-sized and a fraction of the medium-sized instances are optimally solved when considering the constraint programming formulation of the problem. Moreover, the commercial solver is able to deliver feasible solutions for the large-sized instances that are of the size of the instances that appear in practice.

Recommendations

• Metaheuristics for the online printing shop scheduling problem
• A MILP model for an extended version of the flexible job shop problem
• Optimal scheduling for flexible job shop operation
• Mixed integer programming models for job shop scheduling: A computational analysis
• Modeling realistic hybrid flexible flowshop scheduling problems

Cites work

• A MILP model for an extended version of the flexible job shop problem
• A heuristic to schedule flexible job-shop in a glass factory
• A research survey: review of flexible job shop scheduling techniques
• A symbiotic evolutionary algorithm for the integration of process planning and job shop scheduling.
• A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem
• An update on the comparison of MIP, CP and hybrid approaches for mixed resource allocation and scheduling
• Evaluation of mathematical models for flexible job-shop scheduling problems
• Failure-directed search for constraint-based scheduling
• Handbook of constraint programming.
• IBM ILOG CP optimizer for scheduling. 20+ years of scheduling with constraints at IBM/ILOG
• List scheduling and beam search methods for the flexible job shop scheduling problem with sequencing flexibility
• Mathematical models for job-shop scheduling problems with routing and process plan flexibility
• Scheduling. Theory, algorithms, and systems.
• The Complexity of Flowshop and Jobshop Scheduling
• The multiperiod two‐dimensional non‐guillotine cutting stock problem with usable leftovers

Cited in

(14)

• The production scheduling problem in a multi-page invoice printing system
• Optimal decomposition approach for solving large nesting and scheduling problems of additive manufacturing systems
• A reactive iterated greedy algorithm for the no-wait flowshop to minimize total tardiness
• A new variable neighbourhood search with a constraint programming search strategy for the open shop scheduling problem with operation repetitions
• Resource optimization in mass casualty management: a comparison of methods
• Metaheuristics for the online printing shop scheduling problem
• The sample analysis machine scheduling problem: definition and comparison of exact solving approaches
• A constraint programming-based iterated greedy algorithm for the open shop with sequence-dependent processing times and makespan minimization
• Scheduling multi-colour print jobs with sequence-dependent setup times
• A simulation-optimization framework for generating dynamic dispatching rules for stochastic job shop with earliness and tardiness penalties
• Scheduling wagons to unload in bulk cargo ports with uncertain processing times
• An algorithm selection approach for the flexible job shop scheduling problem: choosing constraint programming solvers through machine learning
• An evolution strategy approach for the distributed permutation flowshop scheduling problem with sequence-dependent setup times
• Integer Linear Programming and Constraint Programming Approaches to a Template Design Problem

Describes a project that uses

Uses Software

• ILOG SCHEDULE
• CPLEX

This page was built for publication: Mixed integer linear programming and constraint programming models for the online printing shop scheduling problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2664355)