Multi-Agent Scheduling for Mass Customisation Using Ant Colony Optimisation
Image: © greenbutterfly / Adobe Stock
Multi Agent Systems
When describing agents in this context, we aren’t referring to someone with dark sunglasses and ear phones hanging down the back of their neck working for MI5. And no, they don’t work with landlords to get new tenants, nor do they help Cristiano Ronaldo sign a new contract with Manchester United. On the contrary, we are referring to an autonomous entity. This entity is capable of observing an environment through a sensor and based on the information gathered, can intelligently impact the environment with the objective of meeting a predefined goal. So, how is that any different from the fictitious MI6 agent, James Bond? Not by very much, I don’t think.
Now that we have cleared up what agents are, we can go ahead to define multi-agents as a group of agents working together to achieve a goal. Multi Agent Systems (MAS) are part of a branch of Artificial Intelligence referred to as Distributed Artificial Intelligence. MAS have been proved in industry to be an effective approach to resource allocation problems because of their coordination and social abilities. In addition, multi agent techniques have been intensively studied and widely applied in many fields of human society and have made their mark in manufacturing applications over the years [Huang, Zhang, Dai, Ho, & Xu, 2009]. In addition, Intelligent Agent Technology was proposed as a viable solution for the development of complex distributed systems; a step forward from objects and traditional Object Oriented Programming [Jarvis, Ronnquist, & Jain, 2013]. MAS have the potential to deal with the problems associated with the customer-driven manufacturing environment otherwise known as Make to Order (MTO).
Since their introduction, MAS have been used to provide an element of realism in military training, for example, realistic group behaviour of targets when fired upon, the incorporation of fatigue and fear, incorporation of legal and political considerations [Jarvis et al., 2013].
If you’re starting to envision video games and some childhood action movie at this point, you need to slow down because you’re getting too far ahead.
One of the biggest arguments about MAS in manufacturing has been the evidence of industrial implementation. Researchers have speculated that one contributing factor has been the difficulty in identifying areas where the paradigm provides a clear value.
Can we really put a man on the moon and we are unable to figure out how to put an agent in factory?
Arguably we can, because MAS have been used in manufacturing, process control, system diagnostics, transportation logistics, and network management (Greenwood, Buhler, & Reitbauer, 2006). More recently, in the Instantly Deployable Evolvable Assembly Systems (IDEAS) project [Onori, Maffei, Durand, Engineering, & Royal, 2013], a multi agent control system demonstrated an assembly system that operated with distributed control; a self-configured system that could be re-configured on-the-fly. As with the resistance to autonomous vehicles, surgery, and more generally AI, the implementation of MAS has been limited in factories because of the high impact of failures. For example; in the case of an automotive plant with a takt time of 1 minute making a car worth £10,000, the cost of disruption to that line would be in excess of £10,000. That figure could easily grow uncontrollably if other costs i.e. labour costs, energy costs etc. are taken into consideration. Whilst this costs could have a huge impact on the profit margins for the manufacturers, it is important that these decisions are not made out of fear of failure. In our missions to the moon, 10 failures preceded the first success and 14 failures before the next success.
To avoid controversy, sending a man to the moon is probably not the same as manufacturing a car but the point here is that failure does not always imply impossibility.
The Impact of Industry 4.0
With the increasing digitalisation of the manufacturing value chain also known as Industry 4.0 and the upsurge in diversity of customer demand – Mass Customisation, the scope and complexity of manufacturing is expected to change. Traditional manufacturing systems characterised by low flexibility, high volume and low variety are not capable of meeting this type of demand. Furthermore, Mass Customisation can complicate assembly processes and when ineffectively managed, can lead to a decline in profits, market position and growth for manufacturers – thus rendering them less competitive. Consequently, developing effective strategies for improving manufacturing systems and operations is an ongoing concern for plant managers and researchers.
In addition to the complexity arising from the introduction of high product variation and shorter product life cycles, manufacturing scheduling should be performed in the face of a high degree of uncertainty in regards to product pathways through the manufacturing system, availability of machines or resources etc. This could create huge bottlenecks especially in regards to material handling if not effectively managed. There is therefore a need for an optimal scheduling technique that will facilitate the effective utilisation of resources and reconfiguration of manufacturing schedules. MAS, due to their inherent capability to adapt to emergence without intervention can be used in this domain to support flexibility, adaptation and re-configurability [Barbosa & Leitao, 2011].
The Significance of Multi Agent Systems in Manufacturing
Assembly is a key element of manufacturing – up to 50% of direct labour cost; using MAS to identify the Optimum Build Sequence has the potential to increase productivity which could materialise into cost savings for assembly operations since operational complexity is reduced. In addition, using AI techniques in manufacturing facilitates the use of intelligent systems and the development of self-sustaining manufacturing systems leading to optimised production quality, huge reductions in down times and energy savings. Furthermore, SMEs often lack access to technologically mature solutions due their limited resources. At HSSMI, we engage in industrial research that is strategically poised to support OEMs and their SME supply chain partners by integrating isolated cells as a fully integrated, optimised production flow leading to less complex relationships among suppliers, manufacturers and customers. By the same token, the emergence of Industry 4.0 provides a digital value and supply chain that promotes internationalisation – a vital requirement for SMEs to prosper globally.
Our MAS Methodology
One of our research objectives is to increase productivity by using MAS to sequence highly heterogeneous customer orders for our manufacturing partners. The MAS identifies the Optimum Build Sequence for customer orders using the Ant Colony Optimisation method (described in the next section) to create a production schedule that minimises the impact of variation induced operational complexity in assembly operations. These concepts have been validated through SME engagements events and use cases from a UK-based automotive OEM.
Ant Colony Optimisation
Ant Colony Optimisation (ACO) is inspired by the foraging behaviour of real ant colonies. Ants, like most social insects, live in groups and a core objective for this group to remain functional is that they have food (You may find that this objective holds true for Homo sapiens as well).
In their quest for food, there emerges a natural optimisation where ants are expected to balance food and energy expended. Hence for this task, the ants are expected to find the shortest path to and from the food source. The table below highlights a comparison between the individual capabilities and group capabilities of ants.
Ant Communication is based on chemicals produced by the ants called “pheromones”. The social behaviour of ants is driven by trail pheromone deposited while walking between food sources and the nest.
Each ant deposits a pheromone trail that increases the probability of the next reaching the decision at point A to follow the path A-B1-C since this path has a higher concentration of pheromone. Generally, ants will choose to follow trails with higher pheromone levels with a higher probability than trails with lower pheromone levels. As more ants use a path, the pheromone trail grows stronger and the path becomes increasingly attractive.
This mechanism is useful in solving optimisation problems and is applicable to multiple domains. Combining this mechanism with the MAS described earlier makes it a robust approach for optimising build sequences for highly variant customer orders in a mixed model assembly line, such that the operational complexity of the assembly line is minimised. This is particularly useful for Mass Customisation since the system now possesses self re-configurability. More importantly, this type of hybrid system characterises the factory of the future and could be a competitive advantage for many manufacturers.
As with real ants, our artificial ants strive to find the best path i.e. product sequence that attract minimal operational complexity. Combined with the strength of agents, an ant can be modelled as an agent capable of finding best sequences within the system with the additional capability of negotiating for resources i.e. assembly workstations, forklifts, parts etc. Modelling assembly systems in this way allows us to tackle many industrial problems, especially as we approach the fourth industrial revolution.
If you found this interesting get in touch with the author Olatunde Banjo (Olatunde.email@example.com)
For more news, follow us on Twitter and LinkedIn or sign up to our newsletter.
Contact us today for a short initial conversation on how HSSMI can help your organisation achieve its strategic goals.