The Multi Crane Scheduling Problem: A Comparison Between Genetic Algorithms and Neural Network approaches based on Simulation Modeling

Naomie Bartoli , Roberto Revetria, Emanuele Morra , Gabriele Galli and Edward Williams

Department of Mechanical Engineering, University of Genoa, Via Opera Pia 15, Genoa, 16145, Italy

Department of Industrial and Manufacturing Systems Engineering, University of Michigan-Dearborn, 4901 Evergreen Rd., Dearborn, MI 48126, USA*

Corresponding author. Email address: [email protected]

ABSTRACT

The internal logistics for warehouses of many industrial applications, based on the movement of heavy goods, is commonly solved by the installment of a multi-crane system. The job scheduling of a multi-crane is an interesting problem of optimization, solved in many ways in the past: this paper describes a comparison between the optimization by the use of Genetic Algorithms and the machine learning piloting driven by Neural Networks. A case-study for steel coil production is proposed as a test frame for two different simulation software tools, one based on heuristic solution and one on machine learning; performances and data achieved from reviews and simulations are compared.

Keywords:

Crane, Genetic Algorithm, Neural Network, Simulation.

1. Introduction

The presence of more than one overhead bridge crane sharing the same runway girders, virtually over the same served area, represents an enormous advantage in terms of efficiency for the operations, but concurrently markedly increases the complexity in jobs scheduling, with relevant consequences for plant and workers’ safety. The digitalization of production processes opens numerous research themes with the ultimate aim of reaching a higher level of repeatability and efficiency of the plant. As regards the whole manufacturing factor, the bridge crane is a fundamental component of every plant, as it must guarantee the movement of the processed objects or its components from one workstation to another, minimizing delays and other inefficiencies. To date, themanagement of overhead traveling cranes still persists in manual mode for a number of reasons, mainly related to the safety and extreme conditions of these systems such as temperature, dust, and the handling of generally heavy or unwieldy objects. Nonetheless, the latest developments in the field of sensors and the implementation of interventions today explore the possibility of a completely automatic management of the movement of the bridge cranes, in particular applied in the park area. This area is organized in large stacks containing different types of scrap and is dominated by a bay on which at least two bridge cranes move; their exact number depends on the size and complexity of the system. Their hooks (mechanical or magnet) enable picking up and depositing the material.

In general, the scheduling of overhead crane movements is an optimization problem, given the data of a list of jobs (withdrawal-deposit); the goal is about finding the best overall sequence with the assignment of single jobs to give the completion of all the jobs in the shortest possible time. This theme is particularly interesting in the scrap park area for coil steel production plant, where, unlike the melt shop, at a given time it is typical to have very long job lists to get a basket, so dozens of missions are needed for one goal.

Crane transport is the most important logistical transport method in the steel production process which has the function of catching, hoisting, and delivering scrap loads. The planning of the bridge crane has become the key to any production procedure and represents a decisive factor in the production process operates stability and high efficiency in the workshop of reliability.

The programming problems of metallurgical cranes are mainly focused on how to solve the spatial conflict between cranes. Research methods based on mathematical programming methods, heuristic methods, simulation methods and intelligent hybrid programming algorithms have been used. It is therefore necessary to study a method that could simultaneously and effectively eliminate the spatial and temporal conflict between cranes (Ma et al. 2010). Finding optimal solutions to planning problems is generally a difficult proposition as it entails combinatorial optimization and is often strongly NP. The problem of programming cranes is no exception to this: it is an NP-hard problem. Therefore, simulation is a suitable tool for studying complex materials management systems.

In this paper, a comparison between two different approaches is proposed to be analyzed in parallel on a test frame offered by a simulation model: the first is given by the application of a wizard for optimization based on Genetic Algorithms and the second is the application of machine learning for piloting the multi crane by a Neural Network. The comparison is currently still on a qualitative level and the paper proposes a test frame for further performance comparisons. Quantitative results from the Genetic Algorithm solution are shown, while hypotheses on the NeuralNetwork approach results are described, taken from general evaluation and results by commercial solutions. The next development of this paper will be focused on the set up of a model based on the same test frame, but in which multi cranes are moved by an AI application. Hence a quantitative comparison between both will be available.

2. State of the art

Due to the growing need to accelerate warehouse handling operations, many recent studies have focused on programming multiple cranes operating simultaneously within the same area (typically understood to mean “bay;” i.e., the cranes share rails). A literature review was carried out according to the following stages:

1. 1. identification of keywords and their combinations;
2. 2.selection of a source database;
3. 3.analysis of the results.

As regards phase one, the following words were chosen: simulation, optimization problem, objective function minimization, bridge crane scheduling, genetic algorithms. The research was applied to the article title, abstract and keywords. In research phase two, several abstracts and databases of citations of literature were selected. At the end of this phase, about 20 articles were collected. During phase three, a new systematic analysis of the basic specifications was carried out and specific papers in the references have been finally selected.

The topic was already covered in the early 2000s, duringwhich proposals arose to study the programming of cranes in a port environment with spatial constraints with the goal of finding the crane-job combination that maximizes productivity. Zäpfel et al. (2004) presented new ideas with the aim of increasing the efficiency of the steel supply chain, by improving warehouse management, concerning the handling of different types of steel coils with the help of overhead cranes with time constraints. This study aimed to minimize processing time, the last order completion time during the planning period and labor costs. To do this, due to the complexity of the study, amixed-integer mathematical-nonlinear optimization model was created. Furthermore, the problem was formulated in terms of job shops to represent all the dynamic situations of the warehouse processes (logistics center). The sequencing problem was studied in 2014 by Graunke et al. (2014), based on a multi-crane programming problem in a coils warehouse. Indeed, for problems on a larger scale, the heuristic algorithm generates quick, robust and acceptable solutions. The genetic algorithms were also used for the optimization of the integrated programming of overhead cranes and storage platforms at the automated container terminals. This article introduced a genetic algorithm capable of performing integrated programming of quay cranes, automated guided vehicles and handling platforms; in particular, this work is oriented towards container terminal applications. In fact, this study aimed to optimize the container stacking process, which is the motivation to save space. The results obtained with the genetic algorithm method have shown higher performance when the programming horizon increases. The programming of the movements of the bridge cranes over time has therefore been studied with different methods and approaches; only some of the methods used in different work environments will be reported below.

The use of machine learning and Artificial Intelligence in multi-crane driving is as yet a task unconsolidated in the literature, even if early studies and commercial solutions based on model simulation are appearing on the market. On the contrary, job scheduling problems in manufacturing have been studied via machine learning for many years. The works by Jain et al. (1998) and by Weckman et al. (2008) are expressions of this and specific system architectures in this direction have been evaluated. Results emphasize that the solution through a Neural Network scheduler provides performances very close to a Genetic Algorithm scheduler, with the well-known properties of AI to be able to learn and adapt to variations in initial condition.

Research from Xie et al. (2014) takes into consideration a multi-crane programming problem commonly encountered in real warehouse operations in steel companies’ warehouses of steel coils. A certain set of coils must be recovered in the designated places: if a requested coil is in the upper or lower level without being blocked, it can be taken directly to its designated place; otherwise, the blocking coils must first be moved to another position. The study is to consider at the same time the problem of mixing and the problem of programming the overhead crane since the simultaneous approach could accurately take into account the routing and the time of movement of the crane; therefore the way it could improve the use of the crane, could improve the completion time of the operations. To clearly describe the problem studied, it was first formulated as a mixed model of integer linear programming (MILP); after which some feasible and optimal properties were identified for the assignment of the bridge cranes to avoid collisions. Since a particular case of the problem has proved to be strongly NP-hard, a heuristic algorithm has also been proposed to solve the aforementioned problem efficiently. In the heuristic algorithm program, for each crane, a detailed sequence specifies the order of all the necessary coils and the position of each block coil to be repositioned. To evaluate the performance of the heuristic, three lower limits are obtained according to the different cases. Furthermore, the strategy of the composite constraint of the lower limits has been adopted to converge toward an optimal value as they are mutually complementary and none of the lower limits can dominate the others. Based on the narrower lower limit, the worst performance limit of the proposed heuristic algorithm is analyzed. The results showed that for small-scale problems, MILP can achieve slightly better high-quality solutions than heuristic solutions. For problems on a larger scale, the proposed heuristic algorithm can quickly generate robust and acceptable solutions.

In order to solve the NP-hard problem of overhead crane programming, the work by Ma et al. (2010) presents a method of simulating crane programming in the steelworks workshop based on the Multi Agent System (MAS). The scheduling system mainly includes groups of agents for overhead cranes, groups of agents for workstations and agents for managing coordination. MAS can decompose a complex and large system into many simple agents that have a simple structure, can interact with each other and can be easily managed. MAS introduces the global objective to match the programming strategies and operating results of the overhead crane with the global objective and the production practice in the workshop. Based on the analysis of the production process, on the methods of organizing production and on the characteristics of the current programming of the cranes in the steelworks workshop, the MAS applied in the operation of the steel bridge cranes is feasible because:

1. 4. The MAS uses the “bottom-up” design method which accords with the rule of formation of the overhead crane programming system;
2. 5.The MAS according to the structural characteristics of the different levels is in accordance with the distributed structure of the bridge crane programming;
3. 6.The autonomy and adaptability of MAS accord with the intelligence of each unit in the overhead crane programming system;
4. 7.MAS can combine with various types of advanced information technology, artificial intelligence technology and so on, which then complement each other.

Each agent has its corresponding rules. The research shows that the simulation method based on the MAS is feasible and can meet the demand of the bridge crane in a timely and effective way and reduce the average transit time of materials and can describe the characteristics of the overhead cranes in the steel mill efficiently.

The document by Lim at al. (2002) examines the programming of overhead cranes for ports through the Tabu Search (TS) method, a search procedure that proceeds iteratively from one solution to another by moving to a “neighbourhood space” with the help of adaptive memory. Probabilistic Search for Tabu (PTS) is a variant of the basic TS, which places more emphasis on randomization than the basic TS. TS operates through neighbourhood shifts, which proceed from one solution to another at each iteration. In the basic TS method, some shifts are taboo marked and prohibited, unless they lead to highly desirable results. Rather than using deterministic strategies, PTS can be used to select movements based on the status and ratings assigned to them by the basic TS principles. The basic approach is to create move assessments that include references to the taboo status and other relevant prejudices of TS strategies using penalties, modifying the decision criterion and selecting the next move among the neighborhood moves that are based on values of different evaluation. From the experiments, the comparison and the above analysis, it is therefore believed that the Tabu Probabilistic Research is a good heuristic method to find good solutions to the programming problem of the bridge cranes.

The paper by Yuan et al. (2017) proposes an efficient network flow model based on events and time spaces with lateral constraints for the problem of programming the overhead crane in a coil warehouse when the overhead crane must undertake a series of requests for storage, recovery and mixing of the reels, and determine the sequence of management of these requests as well as the positions to which the reels are moved. The goal is to minimize the makespan (the time needed to execute all the requests); in fact, the problem of programming the overhead crane is optimized by minimizing the actual working time to avoid unnecessary movements. Not only optimization for the handling time of each request, but also for the space in which for storing the reels is required; so a new space-time network flow model is required, that uses the strategy of continuous time modelling in a space-time network, which can be optimally solved by a conventional MIP solver for small cases and medium size in one minute. Due to the NP-hard characteristic of the problem, a dynamic programming approach has been designed exploiting the structure of the problem, on the basis of which an approximate dynamic programming algorithm (ADP) is developed to obtain almost optimal solutions. The results, through computational experiments, showed that the proposed model for space-time network flow can be solved much faster than the traditional planning model and the standard model for space-time network flow.

Xie et al. (2015) solve the programming problem of a bridge crane as presented in the warehouse of cold rolling material in a steel company. The goal, as before, is to minimize the makespan. Since the problem is NP-hard, a genetic algorithm has been presented to offer a reasonable quality of the solution. The exploration process is performed by two genetic operators: the crossover and the mutation. GA starts with a population of individuals and each solution is called a chromosome, which is made up of genes that represent decision variables. The chromosome representation used in this work shows that each coil in the program is a chromosome gene. Ten instances have been resolved to test the performance of the proposed GA. For most smaller cases, GA can achieve an optimal solution. As the problem size or space usage increases, the GA solution time is longer. The performance of this algorithm has been demonstrated efficiently and effectively. It provides a solution to improve the efficiency of the bridge cranes and the productivity of the steel company in the warehouse.

3. Materials and Methods

3.1 General Description

The steel plant is divided into several bays and, in this elaboration, we have focused on the analysis of the scrap park which represents the area where the material is stored awaiting loading into the kilns. The shed analyzed is characterized by several stalls (sheet pantograph, turning, pre-reduced, naval, etc.) and each of these represents a possible starting point for the scrap. In addition, there are three preparation points where the scrap baskets are then prepared.To move, after loading the scrap in the various stalls, and unloading it subsequently in the baskets, there are three overhead traveling cranes that travel on a single track. Real dimensions for the shed are the length of runway, 213m and the respective width of runway, 63m.

3.2 Scheduling Problem

In the scrap park, overhead cranes must manage mainly:

• The supply of scrap, moving it from trucks/flights to stacks in dedicated bays,●
• Loading the scrap, moving it from the stacks to the baskets (or conveyor belts) which then deliver the scrap to the melting furnace, following asuitable and predetermined succession by type.

Three overhead cranes share the same runways and are engaged by the simulation scheduling system. The task of the system is to provide scrap materials to specific baskets, starting from different sources according to a specific recipe, needed for the final product (steel type) to be produced. The overall process flowchart is shown in figure 1.

3.3. Test Frame for Multi Crane

3.3.1. Simulation Model 

As previously described, the plant studied is a scrap park and is characterized by several areas that represent the possible starting points for the scrap handling. The transport of the scrap from the different areas to the baskets takes place by means of three overhead cranes that move on one set of rails. A standard object from a common simulation software library is used. Particularly, the software used is Tecnomatix Plant Simulation (Mes 2017). The real features of the shed have been attributed to the model frame, so the geometric scale is one-to-one relative vs the model. An initialization function called at the beginning of the simulation lists into a table column all the portal cranes desired and creates their frame logic and 3D counterparts. The portals need other functions to take the mobile unit (hoist load), then the object, and takes it from the station where it was originated to the arrival station. In the specific case, it allows to take the scrap from the various stalls and to take it to the scrap baskets. The scrap park is made up of several stations, so there are more starting points where the scrap is available. These areas are modelled as buffers with an infinite capacity assigned. A structure is therefore built in and the starting points are arranged in matrix format. The same procedure is used to represent the scrap baskets which, unlike the scrap pick-up points, are connected to a drain block and then are to be deleted. The base is to create recipes and a function that reads recipes data from a table is provided. This table refers to one of the preparation points, therefore in the specific case to the three scrap preparation points which are the baskets. This table consists of two columns: a first column where each row represents a location, i.e. a scrap pick-up point (i.e. the buffers), and a second column that contains a number, which indicates the number of catches that must be done in that location.

A queue is created for each portal crane with the following features:

• A function to take the first object of the queue, which is then removed;●
• A function which allows the analyst to add an object;●
• A function to take the first object at the top, but it does not remove it and therefore the analyst can see it infinitely often.

The recipes are provided for more than one basket depending on the type of steel to be made. The scrap pick-up location and the number of pick-up tasks for each location will be provided for each recipe. The traveling salesman problem can be compared to thescheduling problem for the loading of scrap baskets. In the traveling salesman problem, the aim is to find an optimal sequence of points to visit such that the sum of the distances to go from one point to another is minimal. The problem relating to the loading of the scrap baskets is similar, in the sense that there is a sequence of operations to be carried out, specifically the movements with the bridge crane, with the difference that the sum of the times necessary to load the baskets must be minimized instead of minimizing the sum of the distances to be covered. To do this, genetic algorithms will be used for their properties in this first customization of the test frame for the comparison with the Neural Network approach. A table that indicates the sequence of tasks and a function that indicates the goodness of our solution are created. In the case studied, the function will be the completion time of the baskets which, to minimize it, will need to optimize the problem and then sequence the baskets. For the fitness function, a method will be created to communicate with the GA optimization tool from the software library described in the next paragraphs. The table, which will be used to configure the model to read the sequences, will define the sequence in which we will do the preparation of the baskets. The assignment ofthe basket target is needed, since in the system studied there are three places to prepare them.

3.3.2. Genetic Algorithm Solution 

The use of Genetic Algorithm is an efficient solution because the optimization task in object has a large number of variants of different solutions In the specific case, a GA wizard is instantiated to integrate genetic algorithms into the test frame of the simulation model. The solutions generated by the Genetic Algorithms wizard object are passed to the simulation model, which in turn will be configured accordingly. Standard libraries form the simulation software are used. At the end of the simulation run, the test frame model transfers the resulting fitness value to the GA wizard object. When the Genetic Algorithms creates individuals, who define the same parameterization, the GA wizard recognizes it and uses the fitness values of the individuals already evaluated. Performing optimization therefore does not waste additional time for multiple assessments of an individual. A first important advantage compared to classical methods is the immunity of genetic algorithms to the number of variables, whereas classical numerical methods are often imprecise due to rounding errors which increase rapidly as the number of variables increases. GA are often used in problems where the objective function depends on a large number of variables, typically five or more. A second, but no less important, property of these algorithms is that the method of finding the solution does not presuppose any type of linearity of the problem, so it is also possible to face problems in which one or more non-linearities exist, possibly also in the form of constraints. Practically, the GA wizard object will do the sequencing, as well as the optimization, starting from the initial orders list; this sequencing represents the initialization of the simulation.

3.3.3. Neural Network Solution 

The Neural Network approach under study requires a specific work, intended as a prosecution of the present paper. The scheduler will be created using the system architecture in Figure 2.

The Neural Network suitable for this aim is the Multi-Layer Perceptron (MLP) with one hidden layer and trained using back-propagation algorithm. Regarding the simulation model, the test frame will be implemented with the following scheme:

• Creation of a connection between the model and the external neural network, to be developed on a software-specific platform (data must be collected continuously in the simulations before specified actions);
• Use of the model test frame to test the NN training algorithm;
• Testing the NN driving system for cranes on the same data set used for the GA solutions.

4. Results and Discussion

4.1 GA performances evaluation

The results from the model simulation for the case-study are shown in Figure 3, with a table reporting optimization results. In particular, the solution represents the best sequence of operations that minimize the fitness function which is intended as the sum of process and delay times contained in the column “Delay”.

The fitness function best value is 28.55 and the trend is reported in Figure 4.

To reach the optimal value 15 generations with 20 individuals per population and five generations per individual has been chosen empirically. Multiple solutions for each generation are shown in Appendix A.

From the final results of simulation, Generation Four has gained the best individual results for optimization and these results are shown in Figure 5.

4.2 Experimental NN performances evaluation

In the hypothesis of this paper, performances very close to GA ones are expected with the neural network approach. A peculiar expected result, to be quantitatively inspected, is the capability of the NN scheduler to quickly react to scenarios never seen before. From commercial feedback collected so far, a performance gain of 50% to 70% is expected, compared to other optimization methods.

5. Conclusions

References