Production Scheduling Approaches
Read these sections, which highlight key problems in production scheduling. How can job sequencing and priority rules help to alleviate the key problems? Can you identify the different rules that affect job sequencing and priority rules in operations management?
4. Meta-heuristics for solving the JSSP
4.3. Bees Algorithm (BA) approach
A colony of bees exploits, in multiple directions simultaneously, food sources in the form of antera with plentiful amounts of nectar or pollen. They are able to cover kilometric distances for good foraging fields. Flower paths are covered based on a stigmergic approach – more nectar places should be visited by more bees.
The foraging strategies in colonies of bees starts by scout bees – a percentage of beehive population. They wave randomly from one patch to another. Returning at the hive, those scout bees deposit their nectar or polled and start a recruiting mechanism rated above a certain quality threshold on nectar stored. The recruiting mechanism is properly a launching into a wild dance over the honeycomb. This natural process is known as waggle dance". Bees, stirring up for discovery, flutter in a number from one to one hundred circuits with a waving and returning phase. The waving phase contains information about direction and distance of flower patches. Waving phases in ascending order on vertical honeycomb suggest flower patches on straightforward line with sunbeams. This information is passed using a kind of dance, that is possible to be developed on right or on left. So through this dance, it is possible to understand the distance from the flower, the presence of nectar and the sunbeam side to choose.
The waggle dance is used as a guide or a map to evaluate merits of explored different patches and to exploit better solutions. After waggle dancing on the dance floor, the dancer (i.e. the scout bee) goes back to the flower patch with follower bees that were waiting inside the hive. A squadron moves forward into the patches. More follower bees are sent to more promising patches, while harvest paths are explored but they are not carried out in the long term. A swarm intelligent approach is constituted. This allows the colony to gather food quickly and efficiently with a recursive recruiting mechanism.
The Bees Algorithm (i.e., BA) is a population-based search; it is inspired to this natural process. In its basic version, the algorithm performs a kind of neighbourhood search combined with random search. Advanced mechanisms could be guided by genetics or taboo operators. The standard Bees Algorithm first developed in Pham and Karaboga in 2006 requires a set of parameters: no. of scout bees (n), no. of sites selected out of n visited sites (m), no. of best sites out of m selected sites (e), no. of bees recruited for the best e sites (nep), no. of bees recruited for the other m-e selected sites (nsp), initial size of patches (ngh). The standard BA starts with random search.
The honey bees' effective foraging strategy can be applied in operation management problems such as JSSP. For each solution, a complete schedule of operations in JSP is produced. The makespan of the solution is analogous to the profitability of the food source in terms of distance and sweetness of the nectar. Bees, n scouts, explore patches, m sites - initially a scout bee for each path could be set, over total ways, ngh, accordingly to the disjunctive graph of fig. 2, randomly at the first stage, choosing the shorter makespan and the higher profitability of the solution path after the first iteration.
Figure 5.
The Bees Algorithm model; 6a. the BA pseudo code; 6b. the flow chart of a general BA procedure.
Together with scouting, this differential recruitment is the key operation of the BA. Once a feasible solution is found, each bee will return to the hive to perform a waggle dance. The output of the waggle dance will be represented by a list of "elite solutions", e best selected sites, from which recruited bees, nep, are chosen for exploration from the population into the hive. Researches of patches are conducted, other nsp bees, in the neighbourhood of the selected sites, m-e sites. System maintains, step repetition: imax, where each bee of the colony of bees will traverse a potential solution. Flower patches, e sites, with better fitness (makespan) will have a higher probability for "elite solutions", promoting the exploitation to an optimal solution.