2
Role and Impacts of Ant Colony Optimization in Job Shop Scheduling Problems: A Detailed Analysis

P. Deepalakshmi1 and K. Shankar2

1 Department of Computer Science and Engineering, Kalasalingam Academy of Research and Education, Krishnankoil, Tamilnadu, India

2 Department of Computer Applications, Alagappa University, Karaikudi, Tamilnadu, India

2.1 Introduction

In manufacturing units, the word “assignment” generally indicates a methodology step related to the demand to change unrefined materials into finished merchandise [1]. The Job Shop Scheduling Problem (JSP) is familiar, involving making a calendar for the instrument by exhausting a static reason series in multi‐machine surroundings [2]. At the point when there is a machine breakdown, the real game plan might be moved from a standard program [3]. The effect of starts and finishing up of all work that must be near its standard program is assigned as the outcome durability and is generally controlled as a trustworthiness metric of the arrangement [4]. JSP is an NP‐hard, difficult, combinatorial optimization problem in which finding the problem's optimal solution increments with the intricacy [5]. The present reality is that dynamic JSPs are challenging. Simplified dispatching rules which depend on experience and basic rationale have been broadly received in the industry [6]. The traditional JSP is likewise a static scheduling scenario in which all activities having a place with the equivalent task should be prepared in a singular request and there should be considered to be no gap between one task completing and its successor beginning [7, 8]. The dispatch rules are not commonly ideal timetables. The manufacturing condition is characterized by the accompanying features, which rapidly result in a significantly more mind‐boggling scheduling issue. To settle this issue in scheduling problems, distinctive metaheuristics optimization – that is, genetic algorithms (GA), particle swarm optimization (PSO), and ant colony optimization (ACO) – are considered to solve the JSP [9]. There are four variables to depict the JSP: Arrival Patterns, Number of Work Stations (machines), Work Sequence, and Performance on Evaluation Criterion. There are two sorts of arrival examples: static and dynamic. In the event that the JSP is less unpredictable, a simple graphical display technique (Gantt diagram) is progressively appropriate for introducing the problem with no tenets and showing and assessing paradigm results [10].

2.1.1 Process of JSP

JSP is a working area where n employments need to be set up on m sets of machines with various endeavors [11, 12]. In most amassing conditions, especially in those with a wide combination of things, strategies, and age levels, the advancement of improvement designs is seen as fundamental to achieving this goal. The detailed process of the JSP model appears in Figure 2.1. It incorporates some essential parts:

  • Job: A portion of work that goes throughout a series of operations.
  • Shop: A place for manufacturing or renovation of goods or machinery.
  • Scheduling: Decision procedure aiming to construe the order of processing.

Each processing time of every movement on each machine must be known early, whatever the progression of jobs to be readied [7]. The primary machine is believed to be arranged continually; any action is to be set up on it first. Machines may be latent or, exceptionally, still. A branch and bound algorithm was industrialized in [13] to solve JSP with availability constraints in the case of a single machine. Each machine is accessible for maintenance once in a while, without great distribution of the scale into developments or days and without considering brief detachment, for instance breakdown or support [14].

Schematic illustration of the process of Job shop scheduling Model.

Figure 2.1 Process of Job Shop Scheduling Model.

2.1.2 Problem Description of JSP

Algorithms like GA and PSO in JSP treat great optimal solution. However, they accomplish a major issue as the absence of optimal solution and computational expense. The activities of each job must be handled in the given grouping. Each machine M ⇒ {i = 1, 2, … n} can process at most one activity at once, and at most one task of each job Job ⇒ { j = 1, 2, … n} can be processed at once. A schedule is an allotment of a solitary time period for every operation. Each job has four tasks to be processed and every activity can be processed by any two of the three machines; the JSP can be seen as a collection of 220 JSPs. While JSP comprises just a sequencing problem in light of the fact that the task of activities to the machines is given ahead of time, the Flexible JSP (FJSP) transforms into a routing just as much as a sequencing problem: allotting every task Rij to a machine chosen from the set Mij and requesting activities on the machines so that makespan is minimized.

2.1.3 Assumption of JSP

To solve the JSP objective function, the following assumptions are considered, based on the job completion and delay time.

  • All jobs must be prepared in a sole machine.
  • Each job must be processed in the due time.
  • Each job can be prepared with the immediate time to such an extent that it finishes with direct time.
  • Completion time.
  • Every single task should be appointed to a machine to systematize the capacities on the machines.
  • This JSP does not have parallel processing.
  • The request for processing is not the equivalent and the operations cannot be intruded upon.
  • Setup times of machines and move time between activities are unimportant.
  • After a job is handled on a machine, it is transported to the next machine quickly and the transportation time is insignificant or incorporated into the activity time.
  • Each activity should be handled as a continuous time of a given length on a given machine. The purpose is to discover a calendar; that is, an allotment of the tasks to time interims to machines that have negligible length.

2.1.4 Constraints of JSP

It suggests the processing times of jobs are extending the limit of their starting time. In most of the examination related to planning falling apart jobs, a straightforward direct decay work is acknowledged. Each job Ji contains a lot of functions Li = { Li, … Ln } which must be performed between a ready time (rti) and a due time (dti). The implementation of each function (Lik) requires the utilization of a lot of resources (Pik  ⊆ P) during a time interval (duki) [15]. The start time Stik of function Lik demonstrates when the function may begin to utilize the assets Lik . The constraints of job‐shop setting up problems can be depicted as binary, disjunctive, metric, and point‐based. JSP with machine accessibility constraint is an exceptional issue. The considerable optimization algorithm to calculate the job complete time with machine accessibility is imperative to JSP. The optimization to compute the complete time of employment by considering the machine accessibility requirement means the working time calculation. This constraint Ki  ( qj, qk) = {[a1− a1+] [a2− a2+]…[an− an+]} disjunctively confines the sequential separation between qj and qk . Two unique functions Lik and Ljl cannot be connected unless they utilize distinctive assets. Capacity constraints give rise to disjunctive linear inequalities.

2.1.5 Objective Functions for JSP

JSP in the manufacturing industry has a distinctive objective function, in the light of which a job gets a short time and least energy in a machine. Many objective functions are considered for the exploration work. Some significant functions are investigated below:

  1. Makespan time: The least makespan, as a rule, derives a decent usage of the machine(s). Most of the writing on the job shop issue considers makespan as the scheduling criterion.
    (2.1)equation
  2. Total weighted tardiness: The distinction between a delay and a deferment lies in the fact that the delay is never negative. This objective is in like manner a broader cost work than the total weighted completion time.
    (2.2)equation
  3. Total workload: Considering machines (aggregate of the working occasions over all machines), the aim is minimization of the maximal machine workload (total of the handling times of activities). This implies the total time on every one of the machines working in the production.
    (2.3)equation

From the above equations, the documentation is shown by i ∈ 1,2,…n, is completion time of jobs if Oij (worki) is a summation of the handling time of tasks that are processed on the machine. To give a brisk reaction to the market prerequisites, a smaller makespan is desired, which makes the generation quicker. The total workload implies the total time on every one of the machines working in the process of production. Finally, the most extreme workload is the machine with the most noteworthy working time.

2.1.6 Types of Job Shop Scheduling

JSP has three main types of scheduling models: Flexible Job Shop Scheduling (FJS), Flow Shop Scheduling (FSS), and Hybrid Job Shop Scheduling (HJSP).

FJS: The jobs are affirmed with the goal that at least one execution technique might be advanced. It contains a single machine to process n jobs. The goal of the setting‐up procedure is to plan these n jobs on a single machine with the end goal that a given measure of performance is limited [14, 16].

FSS: Distinctive machines given with the objective that most of the items being processed through this machine go in a comparative request. The machines are normally set up a course of action [17], which includes a flow shop, and the scheduling of the jobs in this condition is typically alluded to as FSS [18].

HJSP: HJSP is normally utilized for industrialized surroundings in which a lot of n jobs are to be handled in a progression of stages, every one of which has a few machines working in a practically identical way [18]. A few phases may have just a single machine, yet somewhere around one phase must have various machines.

2.1.7 Advantages and Application of JSP

This section describes the merits of JSP and discusses some of the real‐time applications.

  • By using all machines completely and successfully, fewer machines are required to fabricate a wide assortment of products. Along these lines, job shop manufacturing needs lower speculation as a result of the relatively smaller number of machines.
  • Improved adaptability in progress planning and augmentation flexibility.
  • Low obsolete quality and decreased time usage of formation of machines and versatile nature of machines.
  • High power to machine disappointments.

Applications

  • Textile industry, bioprocess industry, vehicle manufacturing, parallel figuring, distributed frameworks, ongoing machine vision frameworks, transportation problems, compartment designation of holder terminal, and workforce task, genuine enterprises.
  • Semiconductor manufacturing, food handling, metalworking along with ship scheduling at route locks.
  • Exhausting machines.
  • Operations of CNC cutting mechanical assembly machines.
  • Control of true proportions of execution of machines.

2.2 Ant Colony Optimization

The ACO algorithm created by Colorni et al. got its motivation from genuine ant colony behavior in finding the shortest path from the home to a food source [19]. The ACO metaheuristic created by Dorigo et al. presents the principal features of artificial ants and these highlights have enlivened diverse ant algorithms to tackle hard optimization problems. ACO utilizes artificial ants so as to probabilistically develop an answer by iteratively adding solution segments to fractional solutions. Tasks need to recognize an appropriate machine to process them [20]. Just as ants search for the shortest path to achieve a food source, activities need to scan for the briefest way to achieve machines. The ants' home and the food source are comparable to the activity beginning and end of JSP.

2.2.1 Inspiration of ACO

Swarm knowledge, as discussed in [21], is the order that bargains with regular and counterfeit frameworks made out of numerous people that coordinate utilizing decentralized control and self‐association. Specifically, the control centers on the aggregate practices that emerge from the local communications of the people with one another and with their condition. Instances of systems considered to display swarm insight are provinces of ants and termites, schools of fish, groups of birds, and crowds of land creatures.

Ant colonies, and social insect societies more generally, are conveyed frameworks that, disregarding their individual straightforwardness, present an exceedingly organized social association. Because of this association, the ant colony can achieve complex undertakings. Diverse parts of the conduct of ant colonies such as scrounging, division of labor, brood arranging and helpful transport have motivated various types of subterranean ant algorithms. At the position, ants need to choose whether to turn right or left. Under this circumstance, they may turn right or left. The main ant turning right will achieve the food first and the position appears in Figure 2.2.

Schematic illustration of the inspiration of ACO.

Figure 2.2 Inspiration of ACO.

2.2.2 ACO Metaheuristic

Artificial ants as utilized in ACO are a stochastic solution development methodology that probabilistically fabricates an answer by iteratively including arrangement segments. A stochastic component in ACO enables the ants to assemble a wide range of arrangements and thus investigate a much larger number of arrangements than greedy heuristics.

  • The way the ants in ACO develop solutions for the problem is explained by moving simultaneously and non‐concurrently on a properly characterized development diagram.
  • It characterizes the way the solution development, the pheromone refresh, and conceivable activities are communicated in the solution procedure.
  • An ACO metaheuristic is enlivened by the searching behavior of ant colonies and targets discrete optimization problems. It tends to be utilized to tackle static and dynamic optimization problems. For static problems, the qualities are given when the problem is characterized and does not change while the problem is being unraveled.
  • The traveling salesman problem is a static problem in which the urban areas and relative separations are static.
  • In the case of dynamic problems such as system directing, powerful scheduling problem occasion characterized by the capacity of a few amounts changes at run time, the optimization must be equipped for adjusting on the web to the evolving condition.

2.2.3 Characteristics of Real Ants

Here we will discuss the real ant characteristics in ACO, an algorithm for solving the JSP problems, namely:

  • Each operator is an independent development process using a stochastic policy and aiming to build a solitary answer for the current problem, conceivably in a computationally light way.
  • The thought behind this sub‐division of specialists is to enable the retrogressive ants to use the helpful data accumulated by the forward ants on their trek from source to goal. In light of this rule, no node routing refreshes are performed by the forward ants [21].
  • The foraging behavior of the ant colony can be mimicked to make fake ants to adopt this idea to tackle some realistic designing optimization problems.

2.2.4 Applications

ACO has been connected to numerous combinatorial enhancement issues. The general algorithm is moderately straightforward and dependent on a lot of ants, each creating one of the conceivable round‐trips within the urban cities.

  • In recent years, the enthusiasm of established researchers in ACO has risen dramatically. A few fruitful utilizations of ACO for a wide range of discrete optimization problems are currently accessible.
  • By far the majority of these applications are to NP‐difficult problems; that is, to problems for which the best‐known algorithms that can definitely reach an ideal solution require time that increases exponentially for more pessimistic scenarios of a complex nature.
  • The utilization of such calculations is frequently infeasible, and ACO calculations can be valuable for rapidly discovering outstanding solutions.
  • ACO is broadly utilized in applications such as successive requesting problems, job scheduling problems, vehicle directing problems, quadratic task problems, traveling salesman problems, scheduling problems, and system routing problems to discover an ideal solution.
  • Sharing the constructive phase with local search to acquire a novel ACO calculation that utilizes a heterogeneous colony of ants is very successful in finding the best‐known values in all cases of a generally utilized set of benchmark problems.

2.2.5 Suitability of ACO for JSP

The fitness evaluation or objective solving by ACO described as follows makes ACO suitable for JSP.

  • Problem portrayal which enables ants to steadily manufacture/alter solutions.
  • A constraint satisfaction strategy which powers the development of attainable solutions and the pheromone refreshing standard which determines how to adjust pheromone trail τ on the edges of the diagram.
  • A probabilistic progress principle regarding heuristic popularity and the pheromone trail.
  • Positive feedback represents fast disclosure of good arrangements.
  • The specialists' experience impacts the fabrication of the solutions in the next cycles: utilizing a whole colony of agents offers power to the solution, and the aggregate connection of the agents makes it more effective.

At the same time, we do have the following restrictions on ACO to be used for JSP also:

  • The ACO solution for JSP reaches the solution in an acceptable time. Be that as it may, when the number of jobs and machines are expanded to the stochastic qualities and the measure turns out to be multiple, an ACO solution can be futile.
  • The extensive scale problem of jobs and machines in JSSP means that multi‐threading systems can be actualized by methods for agent innovation.
  • A probability distribution can change for every emphasis and it has a troublesome hypothetical investigation and also dependent groupings of irregular choices.

2.2.6 Implementation Procedure of ACO

The ant state computation is a method for discovering perfect ways that rely on the example of ants chasing down a food source. The major typical for this estimation is that the pheromone worth is updated at all cycles itself by all of the ants included. Applying ant estimation to deal with a couple of issues, the pheromone is used as a medium to trade messages, so the assortment of pheromone has a basic effect to deal with issues. This ACO strategy, with two important procedures which update the pheromone as well as the probability computation, and the flow graph of ACO appear in Figure 2.3.

2.2.7 Implementation Procedure of ACO

2.2.7.1 Initialization

Table 2.1 demonstrates the processing time for 7×7 machines and the processing time in each job comparing machines. In this procedure, starting with one generation then onto the next generation, the crossover and mutation process is rehashed until the most extreme number of generations is fulfilled.

Flowchart depicts ACO.

Figure 2.3 Flowchart of ACO.

2.2.7.2 Probability Transition Matrix

At every single configuration stage, ant c applies a probabilistic activity decision rule, known as an irregular corresponding principle, to figure out which area must be visited next. In particular, the probability with which ant (finish time) c, now in area i, wants to go to area j is:

(2.4)equation

Table 2.1 Job completion time allocation of 7×7 JSP.

Machines Jobs
M1 M2 M3 M4 M5 M6 M7
J1 P1 P2 P4 P3 P6 P5 P7
J2 P2 P4 P3 P7 P6 P5 P1
J3 P7 P5 P2 P4 P1 P2 P6
J4 P6 P4 P1 P5 P2 P7 P3
J5 P2 P3 P7 P6 P4 P5 P6
J6 P3 P1 P4 P5 P2 P6 P7
J7 P1 P3 P4 P6 P7 P2 P5

According to this probability direction, the probability of picking a particular circular segment (i, j) upgrades the estimation of the connected pheromone trail βij and of the heuristic information ?ij, and the parameters α and ? categorize the similar importance of the pheromone versus the heuristic information, which is denoted by δij, the coterminous urban communities further liable to be picked; while if δij = 0, pheromone enhancement is working correctly.

2.2.7.3 New Pheromone Updating Model

While searching for food, pheromones are conveyed by ants and they store them on trails. It is a method used to change the proportion of pheromone based on where the ants went in the midst of the improvement of the game plan. To update the numerical values, the sigmoid limit is induced as a limit which is melded with the fake neural framework.

2.2.7.4 Evaporation Model

The pheromone esteems are refreshed when all the s ants have framed solution after their emphasis. The measure of pheromone is equivalent to Δβij = 0. Over time, the pheromone trail is changed due to new pheromone being connected and old pheromone vanishing. ρ is set as the evaporation coefficient of the pheromone. The pheromone force connected with the edge joining areas i and j is depicted by

(2.5)equation

The locations of ACO are recorded in the tabu list, followed by the memory of ant n is assumed and the term ρ indicates pheromone evaporation rate. Finally, δij is the quantity of pheromone laid on the edge by the nth ant.

(2.6)equation

The speed of this decay is symbolized by ?, which is the evaporation limitation. The correct section upgrades the pheromone on every one of the edges visited by ants. The measure of pheromone an ant stores on an edge is demonstrated by Ln, which indicates the length of the visit created by the related ant. At long last, the evaporation is gauge until the minimization.

2.2.7.5 Termination Model

Until reaching the optimal solution for the JSP process, the model runs to get least makespan time, most extreme tardiness, and average workload. If ants examine different routes, at that point there is a higher probability that one of them will find an improved course of action. From the ant settlement motivated strategy, a perfect course of action will be found by using differing accentuations.

2.3 Review of Recent Articles

This section in Table 2.2 reviews many JSP articles with multi‐objective functions and solved using optimization models. Here, we will prefer ACO techniques for solving the manufacturing problem.

2.3.1 Articles Related to ACO to Solve JSP Objective Function

In 2017, Elmi and Topaloglu [30] recommended the ACO‐based algorithm while deciding the ideal height of jobs in the cyclic timetable, the robot assignments for transportation activities, and the ideal sequencing of the robot's moves, which in return maximizes the throughput rate. The proficiency of the proposed model is analyzed by a computational report on many arbitrarily created problem cases.

In 2018, Engin and Güçlü [17] proposed the hybrid ant colony algorithm (ACA), which is connected to the 192 benchmark occurrences from the literature so as to limit makespan. The execution of the proposed algorithm is contrasted with the Adaptive Learning Approach and the Genetic Heuristic algorithm which were utilized in past investigations to illuminate a similar arrangement of benchmark problems.

A dynamic schedule technique is connected to Dynamic JSP (DJSP) by Meilin et al. [31]. Manufacturing Execution System is an equipment stage sent in the shop floor with the point of constant and remote manufacturing. This approach has been put into genuine practice in a few manufacturing undertakings, as indicated by its all‐inclusiveness. It has proved astoundingly effective in relation to constant scheduling and arranging JIT (Just‐In‐Time) manufacturing.

Table 2.2 Review of recent articles in JSP manufacturing.

Author/Ref Technique Objective functions Description
Reddy and Padmanabhan [22] Teaching Learning‐based Optimization (TLBO) Makespan Time Teacher stage involves learning something from a teacher and Learner phase involves learning without input from another person. TLBO execution can be studied by solving with 10 Taillard benchmark problems.
Ling Wang and Ye Xu [23] Hybrid Biogeography‐Based Optimization (HBBO) Makespan Time In the relocation stage, the way relinking heuristic is used as an item nearby search procedure to upgrade the gathering.
Akram et al. [24]. Fast Simulated Annealing (FSA) Makespan Time This algorithm was tested by attempting to solve 88 benchmark problems taken from previously published research. The proposed algorithm solved 45 problem within a reasonable time and to the best known values. The algorithm also measured against 18 other published works.
Muthiah and Rajkumar [25] Artificial Bee Colony (ABC) Makespan Time ABC algorithm was skilled to achieve staggering outcomes. Similarly, they have explored and separated the run time of the two systems according to the general taking care of the CPU for finishing the total number of accentuation.
Kumar et al. [26] Krill Herd Optimization (KHO) Makespan Time A couple of earlier standards are given to build the underlying population with an unusual value state. This examination used four unique optimization systems to find the best outcomes using the KHO process.
Akram et al. [24] Fast Simulated Annealing (FSA) Makespan Time FSA for worldwide search and stifling, for bounded solutions in the territory of the current solution, while a tabu list is used to prevent the search from coming back to previously examined solutions.
Salido et al. [27] Genetic algorithm Makespan Time Shows an augmentation of the traditional JSP, where every task must be executed by one machine and this machine can work at various rates.
Yazdani et al. [28] Imperialist Competitive Algorithm and Neighborhood Search maximum earliness and maximum tardiness Motivated by various advances in solving this famously troublesome problem, another surmised optimization approach is built up, which depends on the radical aggressive algorithm hybridized with an effective neighborhood search.
Mokhtari and Hasani [29] Enhanced Evolutionary Algorithm minimizing total completion time, total energy cost and maximizing the total availability of the system To adapt to this multi‐target optimization problem, an improved evolutionary algorithm joined with the global criterion is proposed as a method of dealing with a multi‐target system, and execution assessment is performed dependent on a broad numerical analysis.

In numerous applications to hard optimization problems, ACO performs best when coordinated with neighborhood seek schedules since they move the ants' answers to a nearby space [18]. If the ant can do that, it will almost certainly develop increasingly exact nearby ideal states in the forthcoming visits by rehashing the entire procedure again and again and hence improving its misuse capacities. Computational outcomes confirm the enhancements accomplished by the proposed method and demonstrate the prevalence of the proposed algorithm; more than seven of those looked at are effective as regards arrangement quality.

A scientific model which is made out of JSP and Carbon Fiber Reinforced Polymer (CFRP) at the same time is a two‐phase ACA presented by Saidi‐Mehrabad et al. [32]. The problem under examination is NP‐hard. The outcomes demonstrate that ACA is an effective metaheuristic for this problem, particularly for the substantial measured problems. Moreover, the ideal number of both AGVs, as well as rail‐routes in the generation condition, is dictated by the financial investigation.

The traditional ACO algorithm along with a load balancing was introduced for JSP in 2013 by Chaukwale and Kamath [33]. They presented the attained outcomes and examined them with reference to traditional ACO. The proposed algorithm gave better outcomes when contrasted with traditional ACO. To enhance the ACA, inadequacy of poor union and simple to fall in neighborhood optima, a genetic ACA with a master–slave structure was planned by Wu et al. [34]. In this algorithm, ACO is viewed as a master and a GA as a slave. Finally, computational tests dependent on the notable benchmark suites in the paper are directed, and then the computational outcomes demonstrate that the displayed algorithm is powerful in finding optimal as well as near‐optimal solutions.

The objectives that are utilized to quantify the nature of the produced timetables are weighted‐total of makespan, the tardiness of jobs, and splitting the cost. The created algorithms are investigated broadly on genuine information acquired from a printing organization and recreated information by Huang and Yu [35]. A scientific programming model is produced and combined examples t‐tests are performed between attained solutions of the numerical programming model and proposed algorithms so as to check the viability of proposed algorithms.

In 2014, Turguner and Sahingoz [36] expressed the advantages of utilizing ACO for JSP. Since ACO is a memoryless algorithm, it tends to be valuable for frameworks that have memory limitations; the iterative idea of ACO can prompt a worldwide optimum solution. The creators considered N×M JSP in which the number of ants will be the same as a number of jobs, N. However, to all intents and purposes, it should be constrained. The creators likewise expressed that CPU utilization rate and getting stuck in neighborhood optima in some cases have become serious problems. To deal with these problems, static max and min estimation of pheromones is utilized. In the event that the problem occasion of JSP scales up as far as jobs and machines, the writers propose using a multi‐threading method with multi‐agent innovation to decrease the number of cycles and the time for handling.

The quantity of ant clusters is set haphazardly. At each emphasis, each ant beginning at a source vertex chooses one of the unvisited vertices as indicated by the standards of progress that consolidate pheromone level data and heuristic separation between activities [37]. To enhance the time attributes of the ACA and to evade the neighborhood ideal, Chernigovskiy et al. presented elitist ants as 1% of the ants overall. Elitist ants improve the circular segments of best courses found so far. Their test results showed that Elite‐ACO and ACOA+ lessens the general generation life cycle by 5%, notwithstanding the decrease in count time contrasted with traditional ACO and considerably better execution contrasted with branch and bound procedure.

The heuristic value is any of the normal turnaround time, normal response, and waiting time. Clearly, an arrangement with a higher likelihood of higher esteem will get more space in the roulette wheel, leading to a higher decision of determination [38]. The creators have tested their algorithm with 10 jobs with 5 non‐primitive procedures, each requiring a static time and 30 ants, and two emphases as a constant setup to discover normal response and waiting time. The number of ants is decreased to 10 to gauge normal turnaround time in just a single cycle. One can also plan to enhance other CPU‐based parameters like CPU usage and CPU throughput as well as to to consider crude procedures with various entry times that typically happen continuously.

In 2013, Tawfeeket al. [39] used ACO for ideal asset assignment for undertakings in a unique cloud framework with the aim of limiting the makespan. A colossal number of cloud clients – in the millions – offer cloud assets for finishing their assignment. To make the best use of these assets, a productive task scheduling component is in reality required to apportion approaching requests/jobs to virtual machines (VMs). Ants begin their search from a VM at each emphasis, and fabricate answers for the cloud assignment scheduling problem by moving to start with one VM then onto the next for the next task until they get an assignment for all undertakings.

In 2017, Imen Chaouch et al. [40] aimed to limit the worldwide makespan over every one of the plants. This paper was an initial step to manage the DJSP utilizing three variants of a bio‐motivated algorithm: the Ant System (AS), the Ant Colony System (ACS), and a Modified Ant Colony Optimization (MACO), with the intent of investigating more hunt space and accordingly guaranteeing better solutions for the problem.

The ACO algorithm has been produced to unravel the proposed numerical model of coordinated procedure arranging and scheduling. The optimization algorithm is separated into two phases. The scheduling plan optimization algorithm and dynamic crisis circumstance were dealt with by Xiaojun Liu et al. [41]. The scheduling plan optimization algorithm is utilized to get a plausible and upgrade scheduling plan, and the dynamic crisis circumstance taking care of component is utilized to deal with dynamic crisis circumstance; for example, embeddings new parts. The proposed strategy establishes a system of incorporation of simulation and heuristic optimization. Simulation was used to assess the local fitness function for ants by Korytkowski et al. [42]. The technique, dependent on ACO, was used to decide the imperfect distribution of dynamic multi‐attribute dispatching rules to boost job shop framework execution (four measures were examined: mean flow time, max flow time, mean tardiness, and max tardiness).

In 2017, Lei Wang et al. [43] proposed enhancing the makespan for FJSP. The accompanying aspects are done on their enhanced ACO algorithm: select machine rule problems, introduce uniform disseminated component for ants, change pheromone's directing instrument, select node strategy, and refresh the pheromone's system. A real generation instance and two sets of common benchmark occurrences were tried, and correlations with some different methodologies confirmed the adequacy of the proposed improved ACO (IACO). The outcomes demonstrate that that the proposed IACO can give a better arrangement in a sensible computational time.

The computer simulations on a lot of benchmark problems have led to evaluating the value of the proposed algorithm in contrast with different heuristics in the existing literature. The solutions found by Habibeh Nazif [44] were of good quality and exhibited the adequacy of the proposed algorithm. A fairly good solution was created in negligible computation time and, after that, the trail powers were started dependent on this solution.

We can summarize the observations and findings of this literature survey as follows. The majority of research in scheduling job shops has kept to fixed‐course single‐arrange job shop problems. From the literature investigation, the seminal research is the use of new tools, for example ACO algorithms and particle swarm algorithms for JSP with great coding structures [15]. The objective here is to limit the makespan, which is polynomially feasible for two multi‐processor groups, regardless of whether seizures are confined to indispensable time [24, 26]. Researchers have developed an uncommon whole number program in two measurements and demonstrated that in the region of the ideal arrangement of its unwinding, there are constantly necessary cross‐section focuses which structure an ideal arrangement of the number program. In one hybrid JSP each machine had indistinguishable parallel machines with an objective of limiting the makespan time [17].

2.4 Results Analysis

This section analyzes the JSP with different optimization and the ACO model with objective function results with implementation platforms. Generally, a JSP problem can be implemented in Matlab software. Here, the datasets have been taken from http://bach.istc.kobe‐u.ac.jp/csp2sat/jss.

Table 2.3 examines the makespan time of various cases and distinctive research papers; the optimizations are Krill Herd Optimization (KHO) [26], Fast Simulated Annealing (FSA) [24], ACO [17], MACO [35], ACS [40], MACO [40], IACO [43], and ACA [44], with Best Known Solutions (BKS). Benchmark problems were run on various occasions by the techniques using similar parameters, which included worst case, best, and normal makespan. Based on the optimization behavior as well as refreshing procedure, the objective function is tackled and the span of the examples is expanded with a settled time‐out. It simulates the behavior of the two algorithms on genuine problems when the time is confined.

Figure 2.4 and Table 2.4 explain the job consummation time and Gannt chart of case 5 and case 8 respectively. Every machine processed its jobs for a specific time and made note of the minimum completion time. In the benchmark problem FT10, the processing time for jobs in machine 1 and 4 are lower than for other machines. The makespan time for ACO is almost equivalent to the BKS time. Additionally, for all the benchmark problem measures, the hybrid methods give the least makespan time contrasted with independent algorithms. The varieties are for the most part reliant on the progressions of an emphasis value and the makespan period.

Figure 2.5a and b demonstrates that with the maximum tardiness of various cases with optimization problems, the optimal solution can be attained. It decreases the working time of the considerable number of jobs processing in every one of the machines. Job waiting time for Matlab simulation process is low compared to the string evaluation process. Matlab gets the best outcome compared to the others. On average, the waiting time difference is 10–12.56% in the existing technique. In job 5, the Matlab procedure gets the most extreme best tardiness from the MACO and ACO method. In light of the cycle, only the objective functions are illuminated; the varieties mostly rely upon changes of an iteration value and the makespan time period. Figure 2.6 shows the computational complexity of all cases with different optimization techniques, for example in case 10, the CC of MACO [35] is 12 485, its minimum value compared to other techniques, and other cases are similarly represented.

2.5 Conclusion

The ACO algorithms presented here functioned admirably and found an allotment of dispatching rules that gave preferable outcomes for all criteria for only one standard in a whole system. The attained outcomes support the adequacy of using the proposed algorithms for settling JSP. Distinctive arrangements can be made for this problem – for instance, given a makespan threshold, an answer that less energy consumption utilization can be achieved and, vice versa, given an energy consumption threshold, a solution that minimizes makespan can be accomplished by an ACO pheromone and probability updating model. In future research, an ACO hybrid with other swarm optimizations could be considered for the JSP process, with multiple goals such as improving delay, workload, earliness, etc. To consolidate the scheduling hypothesis with every profession characteristic to use to manage the genuine generation, the assistance could be taken from any manufacturing industry case investigation.

Table 2.3 Benchmark problems with objective function.

Cases Size Makespan Time
BKS KHO [26] FSA [24] ACO [17] MACO [35] ACS [40] MACO [40] IACO [43] ACA [44]
Case 1 10×5 666 665 666 666 659 659 688 666 667
Case 2 10×5 677 672 655 678 578 679 678 623 688
Case 3 10×5 597 592 597 560 586 590 593 598 560
Case 4 10×5 590 585 590 585 586 588 589 585 588
Case 5 10×10 593 588 593 575 605 605 590 583 596
Case 6 10×10 945 940 926 942 945 948 942 942 595
Case 7 10×10 784 779 890 786 788 786 783 783 789
Case 8 15×10 842 837 820 845 846 849 840 845 843
Case 9 10×10 902 909 863 905 918 916 910 906 930
Case 10 10×10 1263 1221 1260 1269 1279 1270 1259 1369 1270
Case 11 10×10 951 928 956 953 960 956 950 950 956
Schematic illustration of the model Gantt chart for Case five.

Figure 2.4 Model Gantt chart for Case 5 (10×10).

Table 2.4 Job completion time of case 8 (15×10): sample model.

Job/Machine M1 M2 M3 M4 M5 M6 M7 M8 M9 M10
J1 1 35 37 58 111 115 210 213 213 268
J2 4 87 91 117 133 204 211 215 215 289
J3 35 87 103 120 135 205 215 257 355 394
J4 112 167 168 171 250 254 254 334 421 423
J5 116 201 204 241 251 273 275 334 504 568
J6 118 201 205 295 338 400 403 495 583 587
J7 211 214 214 364 365 404 491 582 660 662
J8 211 215 275 405 407 445 494 606 664 747
J9 213 313 317 405 408 462 497 650 689 796
J10 309 313 320 409 488 565 648 652 732 797
J11 313 341 343 504 504 600 643 728 733 804
J12 374 378 378 506 601 611 644 763 766 820
J13 378 381 440 565 692 693 709 765 812 813
J14 379 385 483 617 692 721 723 815 818 845
J15 466 511 513 617 696 722 762 856 885 843
Bar chart depicts the comparative analysis of Maximum Tardiness.

Figure 2.5 Comparative analysis of Maximum Tardiness.

Bar chart depicts computational complexity analysis.

Figure 2.6 Computational complexity (CC) analysis.

References

  1. 1 Sun, L., Lin, L., Wang, Y. et al. (2015). A Bayesian optimization‐based evolutionary algorithm for flexible job shop scheduling. Procedia Comput. Sci. 61: 521–526.
  2. 2 Pang, H. and Jiang, X. (2017). A solution of Flexible Job Shop Scheduling Problem Based on Ant Colony Algorithm and Complex Network. In Computational Intelligence and Design (ISCID), 2017 10th International Symposium on (Vol. 2: 463–466). IEEE.
  3. 3 Li, L., Keqi, W., and Chunnan, Z. (2010). An improved ant colony algorithm combined with particle swarm optimization algorithm for multi‐objective flexible job shop scheduling problem. In Machine Vision and Human‐Machine Interface (MVHI), 2010 International Conference on (pp. 88–91). IEEE.
  4. 4 Fox, B., Xiang, W., and Lee, H.P. (2007). Industrial applications of the ant colony optimization algorithm. Int. J. Adv. Manuf. Technol. 31 (7–8): 805–814.
  5. 5 Lin, J., Zhu, L., and Wang, Z.J. (2018). A hybrid multi‐verse optimization for the fuzzy flexible job‐shop scheduling problem. Comput. Ind. Eng. 127: 1089–1100.
  6. 6 Xing, L.N., Chen, Y.W., Wang, P. et al. (2010). A knowledge‐based ant colony optimization for flexible job shop scheduling problems. Appl. Soft Comput. 10 (3): 888–896.
  7. 7Huang, K.L. and Liao, C.J. (2008). Ant colony optimization combined with taboo search for the job shop scheduling problem. Comput. Oper. Res. 35 (4): 1030–1046.
  8. 8 Huang, R.H. and Yang, C.L. (2008). Ant colony system for job shop scheduling with time windows. Int. J. Adv. Manuf. Technol. 39 (1–2): 151–157.
  9. 9 Wen‐Xia, W., Yan‐Hong, W., Hong‐Xia, Y., and Cong‐Yi, Z. (2013). Dynamic‐Balance‐Adaptive Ant Colony Optimization Algorithm for Job‐Shop Scheduling. 2013 Fifth International Conference on Measuring Technology and Mechatronics Automation (ICMTMA), 496–499.
  10. 10 Kis, T. (2003). Job‐shop scheduling with processing alternatives. Eur. J. Oper. Res. 151 (2): 307–332.
  11. 11 Ho, N.B., Tay, J.C., and Lai, E.M.K. (2007). An effective architecture for learning and evolving flexible job‐shop schedules. Eur. J. Oper. Res. 179 (2): 316–333.
  12. 12 Zhang, C., Li, P., Guan, Z., and Rao, Y. (2007). A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Comput. Oper. Res. 34 (11): 3229–3242.
  13. 13 Mauguière, P., Billaut, J.C., and Bouquard, J.L. (2005). New single machine and job‐shop scheduling problems with availability constraints. J. Sched. 8 (3): 211–231.
  14. 14 Jensen, M.T. (2003). Generating robust and flexible job shop schedules using genetic algorithms. IEEE Trans. Evol. Comput. 7 (3): 275–288.
  15. 15 Chan, F.T.S., Wong, T.C., and Chan, L.Y. (2006). Flexible job‐shop scheduling problem under resource constraints. Int. J. Prod. Res. 44 (11): 2071–2089.
  16. 16 Kavitha, S., Venkumar, P., Rajini, N., and Pitchipoo, P. (2018). An efficient social spider optimization for flexible job shop scheduling problem. J. Adv. Manuf. Syst. 17 (2): 181–196.
  17. 17 Engin, O. and Güçlü, A. (2018). A new hybrid ant colony optimization algorithm for solving the no‐wait flow shop scheduling problems. Appl. Soft Comput. 72: 166–176.
  18. 18 Kurdi, M. (2019). Ant colony system with a novel Non‐DaemonActions procedure for multiprocessor task scheduling in multistage hybrid flow shop. Swarm Evol. Comput. 44: 987–1002.
  19. 19 Comuzzi, M. (2019). Optimal directed hypergraph traversal with ant‐colony optimisation. Inf. Sci. 471: 132–148.
  20. 20 Jin, H., Wang, W., Cai, M. et al. (2017). Ant colony optimization model with characterization‐based speed and multi‐driver for the refilling system in hospital. Adv. Mech. Eng. 9 (8): 1–18.
  21. 21 Wu, Y., Gong, M., Ma, W., and Wang, S. (2019). High‐order graph matching based on ant colony optimization. Neurocomputing 328: 97–104.
  22. 22 Reddy, K.N. and Padmanabhan, G. (2016). Teaching learning based optimization (TLBO) for job shop scheduling problems. First International Conference on Productivity, Efficiency and Competitiveness in Design and Manufacturing, Coimbatore, Tamilnadu, India.
  23. 23 Wang, L. and Xu, Y. (2011). An effective hybrid biogeography‐based optimization algorithm for parameter estimation of chaotic systems. Expert Syst. Appl. 38 (12): 15103–15109.
  24. 24 Akram, K., Kamal, K., and Zeb, A. (2016). Fast simulated annealing hybridized with quenching for solving job shop scheduling problem. Appl. Soft Comput. 49: 510–523.
  25. 25 Muthiah, A. and Rajkumar, R. (2014). A comparison of artificial bee colony algorithm and genetic algorithm to minimize the makespan for job shop scheduling. Procedia Eng. 97: 1745–1754.
  26. 26 Kumar, V., Singh, O., and Mishra, R.S. (2018). Krill herd based optimization for job shop scheduling problems (JSSP) to minimize make span time. Int. J. Appl. Eng. Res. 13 (11): 9627–9635.
  27. 27 Salido, M.A., Escamilla, J., Giret, A., and Barber, F. (2016). A genetic algorithm for energy‐efficiency in job‐shop scheduling. Int. J. Adv. Manuf. Technol. 85 (5–8): 1303–1314.
  28. 28 Yazdani, M., Aleti, A., Khalili, S.M., and Jolai, F. (2017). Optimizing the sum of maximum earliness and tardiness of the job shop scheduling problem. Comput. Ind. Eng. 107: 12–24.
  29. 29 Mokhtari, H. and Hasani, A. (2017). An energy‐efficient multi‐objective optimization for flexible job‐shop scheduling problem. Comput. Chem. Eng. 104: 339–352.
  30. 30 Elmi, A. and Topaloglu, S. (2017). Cyclic job shop robotic cell scheduling problem: ant colony optimization. Comput. Ind. Eng. 111: 417–432.
  31. 31 Meilin, W., Xiangwei, Z., Qingyun, D., and Jinbin, H. (2010). A dynamic schedule methodology for discrete job shop problem based on ant colony optimization. 2nd IEEE International Conference on Information Management and Engineering (ICIME), 306–309.
  32. 32 Saidi‐Mehrabad, M., Dehnavi‐Arani, S., Evazabadian, F., and Mahmoodian, V. (2015). An ant colony algorithm (ACA) for solving the new integrated model of job shop scheduling and conflict‐free routing of AGVs. Comput. Ind. Eng. 86: 2–13.
  33. 33 Chaukwale, R. and Kamath, S.S. (2013). A modified ant colony optimization algorithm with load balancing for job shop scheduling. 15th International Conference on Advanced Computing Technologies (ICACT), 1–5.
  34. 34 Wu, Z.J., Zhang, L.P., Wang, W., and Wang, K. (2009). Research on Job‐Shop Scheduling Problem Based on Genetic Ant Colony Algorithms. In Computational Intelligence and Security, 2009. CIS'09. International Conference on (Vol. 2: 114–118). IEEE.
  35. 35 Huang, R.H. and Yu, T.H. (2017). An effective ant colony optimization algorithm for multi‐objective job‐shop scheduling with equal‐size lot‐splitting. Appl. Soft Comput. 57: 642–656.
  36. 36Turguner, C. and Sahingoz, O.K. (2014). Solving job shop scheduling problem with Ant Colony Optimization. 15th International Symposium on Computational Intelligence and Informatics (CINTI), 385–389.
  37. 37 Chernigovskiy, A.S., Kapulin, D.V., Noskova, E.E. et al. (2017, October). Production scheduling with ant colony optimization. IOP Conf. Ser.: Earth Environ. Sci. 87 (6): 062002.
  38. 38 Nosheen, F., Bibi, S., and Khan, S. (2013). Ant Colony Optimization based scheduling algorithm. International Conference on Open Source Systems and Technologies (ICOSST), 18–22.
  39. 39 Tawfeek, M.A., El‐Sisi, A., Keshk, A.E., and Torkey, F.A. (2013). Cloud task scheduling based on ant colony optimization. 8th International Conference on Computer Engineering & Systems (ICCES), 64–69.
  40. 40 Chaouch, I., Driss, O.B., and Ghedira, K. (2017). A modified ant colony optimization algorithm for the distributed job shop scheduling problem. Procedia Comput. Sci. 112: 296–305.
  41. 41 Liu, X., Ni, Z., and Qiu, X. (2016). Application of ant colony optimization algorithm in integrated process planning and scheduling. Int. J. Adv. Manuf. Technol. 84 (1–4): 393–404.
  42. 42 Korytkowski, P., Rymaszewski, S., and Wiśniewski, T. (2013). Ant colony optimization for job shop scheduling using multi‐attribute dispatching rules. Int. J. Adv. Manuf. Technol. 67 (1–4): 231–241.
  43. 43 Wang, L., Cai, J., Li, M., and Liu, Z. (2017). Flexible job shop scheduling problem using an improved ant colony optimization. Sci. Prog.: 9016303.
  44. 44 Nazif, H. (2015). Solving job shop scheduling problem using an ant colony algorithm. J. Asian Sci. Res. 5 (5): 261–268.
..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset