Discrete Optimization III

Contributed Session

Time Slot: Thursday Afternoon

Room: 002

Chair: Alessio Sortino

Throughput evaluation of large series-parallel production lines: a fast and efficient approach

Time: 15:40

Yasmine Alaouchiche (University of Technology of Troyes), Ouazene Yassine, Yalaoui Farouk

Introduction
Efficient performance of manufacturing systems is of crucial importance. Throughput evaluation of serial production lines has been largely treated in the literature. In contrast, parallel manufacturing systems are important but complex structures and the literature dedicated to there study is more scarce. Existing studies either use aggregation techniques to transform each parallel station into an equivalent one and then implement serial line evaluation tools, or directly evaluate the series-parallel system through decomposition methods. Nevertheless, Most available methods either study limited and sometimes unrealistic systems (small, unbuffered, or reliable), or require important computational time. Therefore, we propose a fast and accurate throughput evaluation method for large series-parallel production lines with unreliable non-identical machines.

Problem description and solution method
The manufacturing system studied is a series-parallel production line with S parallel machine workstations separated by and S − 1 intermediate buffers of finite capacities. Each workstation Si may have Ki unreliable and non-identical parallel machines following the exponential reliability model. To study the series-parallel system, each parallel workstation is aggregated into an equivalent station using aggregation techniques of parallel machines from the literature ([1], [5], and [3]). After aggregating each parallel workstation into an equivalent station, the throughput of the flow system is evaluated based on the Equivalent Machine Method [4] where buffer states are analyzed using a birth death Markov process. State space cardinality is drastically reduced through the consideration of only full and empty buffer states rather than all buffer states. Then, each station Si is replaced by an equivalent one taking into account the probabilities of blockage and starvation. The throughput of the system is defined as the bottleneck between the effective production rates of all the stations.

Numerical experiments and results
The proposed method is formulated as a non linear program which is implemented on a mathematical solver for conducting numerical experiments. A benchmark introduced in [2] is used to compare the performance of the approach with the evaluation method proposed in [2] against an implemented simulation model on FlexSim.Numerical results of throughput estimation for both balanced and asynchronous configurations with up to 50 parallel workstations, demonstrate the great accuracy and efficiency of the proposed method compared to the evaluation method in [2]. Indeed, the proposed algorithm performs very well with total average errors of 4.91% and 2.64%, whereas [2] evaluation method registers total average errors of 7.87% and 5.41%, for the balanced configurations and the asynchronous configurations respectively. In addition, the computational time for all cases is reduced drastically. Indeed, it ranges between 3.51s up to 15.30s, whereas in [2] evaluation method computational time ranges between 8.2s up to 1.67h.

Conclusion
The proposed approach offers the possibility to evaluate with good accuracy the performance of large complex series-parallel production lines in few seconds. We believe that this evaluation tool could be the key to solving efficiently design problems in real manufacturing systems. Future research includes using the proposed method as an evaluation tool to solve design problems such as the buffer and/or server allocation problem in complex production systems.

[1] B. Ancelin and A. Semery. Calcul de la productivité d’une ligne intégrée de fabrication : Calif, un logiciel industriel basé sur une nouvelle heuristique. Automatique-productique informatique industrielle, 21(3) :209–238, 1987.
[2] A. Diamantidis, J.-H. Lee, C. T. Papadopoulos, J. Li, and C. Heavey. Performance evaluation of flow lines with non-identical and unreliable parallel machines and finite buffers. International Journal of Production Research, 58(13) :3881–3904, 2020.
[3] J. Li. Modeling and analysis of manufacturing systems with parallel lines. IEEE transactions on automatic control, 49(10) :1824–1832, 2004.
[4] Y. Ouazene, H. Chehade, A. Yalaoui, and F. Yalaoui. Equivalent machine method for ap-proximate evaluation of buffered unreliable production lines. In 2013 IEEE Symposium onComputational Intelligence in Production and Logistics Systems (CIPLS), pages 33–39. IEEE, 2013.
[5] A. Patchong and D. Willaeys. Modeling and analysis of an unreliable flow line composed of parallel-machine stages. Iie Transactions, 33(7) :559–568, 2001.

Cluster Deletion Problem

Time: 16:00

Carmine Sorgente (University of Salerno), Ambrosio Giuseppe, Cerulli Raffaele, Serra Domenico, Vaccaro Ugo

Clustering deals with partitioning a given set of items into homogeneous subsets on the basis of their relations. If such items are regarded as the nodes of a graph, the output of the clustering task is a disjoint union of cliques and is also referred to as cluster graph.This talk addresses the Cluster Deletion problem, which aims to identify the minimum set of edges whose removal from the original graph produces a cluster graph. It is known that minimizing the total number of edges between the clusters is equivalent to maximizing the total number of edges within the clusters.The problem belongs to a family of cluster graph modification problems, it finds application in DNA clone classification and is known to be NP-hard on generic graphs.We address the Cluster Deletion problem by designing an Integer Linear Programming formulation and a heuristic approach based on edge contraction operations which iteratively merge promising nodes in order to obtain good quality clique partitions.We finally compare the performances of the proposed approaches on both real and randomly generated instances.

A MILP Formulation and a Metaheuristic Approach for the Scheduling of Drone Landings and Payload Changes on an Automatic Platform

Time: 16:20

Mauro Gaggero (National Research Council of Italy, Geno), Elena Ausonio, Patrizia Bagnerini

We present a mixed-integer linear programming formulation and a metaheuristic approach based on direct search to schedule landings and payload changes of a set of unmanned aerial vehicles that cooperate to achieve given mission objectives. In more detail, such vehicles require landing on an automatic platform able to rapidly substitute batteries and switch the payload they are currently carrying with another one, if required by the mission at hand. Preliminary numerical results are presented to show the effectiveness of the metaheuristic algorithm as a compromise between accuracy of suboptimal solutions and computational effort.

Scheduling Airport Personnel by Exact Optimization Models

Time: 16:40

Alessio Sortino (DINFO, University of Florence), Cappanera Paola, Di Gangi Leonardo, Lapucci Matteo, Pellegrini Giulia, Schoen Fabio

Defining shifts and assigning jobs to personnel in large companies is a common problem, yet not trivial to handle. Effective and efficient approaches have been proposed through the years by operations research experts. In this work, the rostering problem is considered as an activity-based scheduling in the specific case of the ground staff in a large Italian airport. This case study, compared to the classical scheduling problem, shows significant additional complexities, such as highly specialized personnel and great granularity of jobs to be carried out. W ithin this work, exact mathematical optimization models are proposed to tackle this problem. In particular, an integer linear programming model is defined, starting from a set of possible shifts calibrated on the basis of demand. In addition, computationally effective valid inequalities defined on groups of overlapped jobs and clique-based are introduced in order to reduce the computational burden of the ILP solver. Experimental results show how the proposed model is effective and able to produce the desired planning, with good optimality guarantees and the employment of reasonable computational resources.