Metaheuristics for the Online Printing Shop Scheduling Problem

in European Journal of Operational Research (2020)

In this work, the online printing shop scheduling problem introduced in (Lunardi et al., Mixed Integer Linear Programming and Constraint Programming Models for the Online Printing Shop Scheduling Problem ... [more ▼]

In this work, the online printing shop scheduling problem introduced in (Lunardi et al., Mixed Integer Linear Programming and Constraint Programming Models for the Online Printing Shop Scheduling Problem, Computers & Operations Research, to appear) is considered. This challenging real scheduling problem, that emerged in the nowadays printing industry, corresponds to a flexible job shop scheduling problem with sequencing flexibility; and it presents several complicating specificities such as resumable operations, periods of unavailability of the machines, sequence-dependent setup times, partial overlapping between operations with precedence constraints, and fixed operations, among others. A local search strategy and metaheuristic approaches for the problem are proposed and evaluated. Based on a common representation scheme, trajectory and populational metaheuristics are considered. Extensive numerical experiments with large-sized instances show that the proposed methods are suitable for solving practical instances of the problem; and that they outperform a half-heuristic-half-exact off-the-shelf solver by a large extent. Numerical experiments with classical instances of the flexible job shop scheduling problem show that the introduced methods are also competitive when applied to this particular case. [less ▲]

Mixed Integer Linear Programming and Constraint Programming Models for the Online Printing Shop Scheduling Problem

in Computers and Operations Research (2020)

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 ... [more ▼]

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. [less ▲]

An Effective Hybrid Imperialist Competitive Algorithm and Tabu Search for an Extended Flexible Job Shop Scheduling Problem

in 34th ACM/SIGAPP Symposium On Applied Computing, Limassol, Cyprus April 8-12, 2019 (2019, April 08)

An extended version of the flexible job shop problem is tackled in this work. The investigated extension of the classical flexible job shop problem allows the precedences between the operations to be ... [more ▼]

An extended version of the flexible job shop problem is tackled in this work. The investigated extension of the classical flexible job shop problem allows the precedences between the operations to be given by an arbitrary directed acyclic graph instead of a linear order. The problem consists of designating the operations to the machines and sequencing them in compliance with the supplied precedences. The goal in the present work is the minimization of the makespan. In order to produce reasonable outcomes in acceptable time, a hybrid imperialist competitive algorithm and tabu search is proposed to solve the problem. Numerical experiments assess the efficiency of the proposed method and compare it with well-known scheduling algorithms. [less ▲]

An Imperialist Competitive Algorithm for a Real-World Flexible Job Shop Scheduling Problem

in 23rd IEEE International Conference on Emerging Technologies and Factory Automation, Torino, Italy, September 4-7, 2018 (2018, September)

Traditional planning and scheduling techniques still hold important roles in modern smart scheduling systems. Realistic features present in modern manufacturing systems need to be incorporated into these ... [more ▼]

Traditional planning and scheduling techniques still hold important roles in modern smart scheduling systems. Realistic features present in modern manufacturing systems need to be incorporated into these techniques. The real-world problem addressed here is an extension of flexible job shop scheduling problem and is issued from the modern printing and boarding industry. The precedence between operations of each job is given by an arbitrary directed acyclic graph rather than a linear order. In this paper, we extend the traditional FJSP solutions representation to address the parallel operations. We propose an imperialist competitive algorithm for the problem. Several instances are used for the experiments and the results show that, for the considered instances, the proposed algorithm is faster and found better or equal solutions compared to the state-of-the-art algorithms. [less ▲]

A Mathematical Model and a Firefly Algorithm for an Extended Flexible Job Shop Problem with Availability Constraints

in 17th International Conference on Artificial Intelligence and Soft Computing, Zakopane, Poland, June 3-7, 2018 (2018, June)

Manufacturing scheduling strategies have historically ignored the availability of the machines. The more realistic the schedule, more accurate the calculations and predictions. Availability of machines ... [more ▼]

Manufacturing scheduling strategies have historically ignored the availability of the machines. The more realistic the schedule, more accurate the calculations and predictions. Availability of machines will play a crucial role in the Industry 4.0 smart factories. In this paper, a mixed integer linear programming model (MILP) and a discrete firefly algorithm (DFA) are proposed for an extended multi-objective FJSP with availability constraints (FJSP-FCR). Several standard instances of FJSP have been used to evaluate the performance of the model and the algorithm. New FJSP-FCR instances are provided. Comparisons among the proposed methods and other state-of-the-art reported algorithms are also presented. Alongside the proposed MILP model, a Genetic Algorithm is implemented for the experiments with the DFA. Extensive investigations are conducted to test the performance of the proposed model and the DFA. The comparisons between DFA and other recently published algorithms shows that it is a feasible approach for the stated problem. [less ▲]

Automated Decision Support IoT Framework

in IEEE 21st International Conference on Emerging Technologies and Factory Automation (ETFA), Berlin, Germany, 2016 (2016, September)

During the past few years, with the fast development and proliferation of the Internet of Things (IoT), many application areas have started to exploit this new computing paradigm. The number of active ... [more ▼]

During the past few years, with the fast development and proliferation of the Internet of Things (IoT), many application areas have started to exploit this new computing paradigm. The number of active computing devices has been growing at a rapid pace in IoT environments around the world. Consequently, a mechanism to deal with this different devices has become necessary. Middleware systems solutions for IoT have been developed in both research and industrial environments to supply this need. However, decision analytics remain a critical challenge. In this work we present the Decision Support IoT Framework composed of COBASEN, an IoT search engine to address the research challenge regarding the discovery and selection of IoT devices when large number of devices with overlapping and sometimes redundant functionality are available in IoT middleware systems, and DMS, a rule-based reasoner engine allowing to set up computational analytics on device data when it is still in motion, extracting valuable information from it for automated decision making. DMS uses Complex Event Processing to analyze and react over streaming data, allowing for example, to trigger an actuator when a specific error or condition appears in the stream. The main goal of this work is to highlight the importance of a decision support system for decision analytics in the IoT paradigm. We developed a system which implements DMS concepts. However, for preliminarily tests, we made a functional evaluation of both systems in terms of performance. Our initial findings suggest that the Decision Support IoT Framework provides important approaches that facilitate the development of IoT applications, and provides a new way to see how the business rules and decision-making will be made towards the Internet of Things. [less ▲]