Int J Adv Manuf Technol DOI 10.1007/s00170-010-2583-9
ORIGINAL ARTICLE
Sequencing and scheduling of job and tool in a flexible manufacturing system using ant colony opti
mization algorithm
P. Udhayakumar & S. Kumanan
Received: 11 September 2009 / Accepted: 15 February 2010 # Springer-Verlag London Limited 2010
Abstract Many optimization problems from the manufacturing systems are very complex in nature and quite hard to solve by conventional optimization techniques. The theme of this paper is to generate an active schedules and optimal sequence of job and tool that can meet minimum makespan schedule for the flexible manufacturing system. It consists of similar work center which is capable of doing many operations. The tools are stored in a common tool magazine that shares with and serves for several work centers to reduce the cost of duplicating tools in each and every work center. This type of manufacturing system is used for a manufacturing environment in which tools are expensive. To achieve the objective, the jobs and tools are sequenced and scheduled. In this work, non-traditional optimization technique such as ant colony optimization (ACO) algorithm are proposed to derive nearoptimal solutions which adopt the Extended Giffler and Thompson algorithm for active feasible schedule generation. In this paper, the proposed algorithm is used for solving number of problems taken from the literature. The results available for the various existing algorithms are compared with results obtained by the ACO algorithm. The analysis reveals that ACO algorithm provides better solution with reasonable computational time. Keywords Scheduling . Sequencing . Flexible manufacturing system . Ant colony optimization algorithm Nomenclature DT Datum time eik Pheromone level for sequencing
P. Udhayakumar (*) : S. Kumanan Department of Production Engineering, National Institute of Technology, Tiruchirappalli 620 015 Tamilnadu, India e-mail: udhaya_kannan@yahoo.com
FJ i JC JP k m pij tij tik Tik T
Finished operations of a job Job number Job conflict Job to be processed on the work center Operation sequence number Number of work center Probability values Pheromone level for allocation Operation time for kth operation of the ith job Tool number required for kth operation of the ith job Number of tools
1 Introduction Intense competition in the global market for mechanical parts manufactured on machine tools and other metal working equipments has compelled manufacturers to reduce delivery times and quote competitive prices even for relatively small orders. The batch size is ever decreasing, and the need to meet specific customer requirements calls for considerable flexibility in the working of the manufacturing systems. With the need of overcoming these requirements together with the advent of computers, the rapid developments in flexible manufacturing system (FMS) have emerged as highly competitive manufacturing strategies of the late twentieth century. An FMS is typically defined as a set of numerically controlled machine tools linked by an automated material handling system working under hierarchical control of computers. Because of the versatility of machine tools and very quick cutting tool interchange capability; these systems are quite flexible with respect to the number of part types that can be produced simultaneously and in very small batches. The combination
Int J Adv Manuf Technol
of technologies and approaches to manufacture brought together in FMS is basically aimed at minimized setup time, minimized change over time, reduced work-in process, minimized flow time, minimized idle time of machines and workers, minimized handling time, reduced floor space, simplification of manufacturing, shortened lead times, improved product quality, cost reduction, and improved market responses, etc. To realize the potential advantages of the system, careful attention must be paid to take various decisions to the problems faced during the life cycle of an FMS. One of them is to allocate jobs and required tools to machines with exact time spans, which is often called loading and scheduling problem. This problem deals with the real-time operation of the system after it has been setup during the planning stage. The success of any FMS lies in the design of an appropriate scheduling procedure to optimize the required performance measures of the manufacturing systems.
2 Literature review Scheduling of FMS has been extensively investigated over the last three decades and it continues to attract the interest of both the academic and industrial sectors. Scheduling literature addresses a wide range of problems described with machine environment, job description, and objective function [1, 2]. Although, the evolution of FMS/CIM has complicated the issue, because of its complex nature of working; it will be best suited to produce variety of parts with flexibility of even small lots [3]. Part and tool flows, two major dynamic entities, are the key factors and their management plays important roles in the operation of a FMS. The majority of research conducted on the scheduling problem of FMS generally assumes a part movement policy [4]. Researchers using this part movement approach have focused on a number of issues that are specifically related to the flow of work pieces [5]. The part movement approach can be justified in many cases, where the cost of parts is very high in comparison with the cost of cutting tools required. However, in many batch machining applications, the cost of cutting tools is a significant proportion of the total production cost, sometimes as much as 25–30% [6]. As the budget for tool purchases is limited in general, it is necessary to determine a tool copy configuration that can give the best system performance for a given limited tool budget [7]. Therefore, by adopting appropriate tooling strategies and economizing on the tooling cost, large reductions in the total cost is feasible [8]. A few researchers gave extensive surveys on the tool management issues of automated manufacturing systems, and emphasize that the lack of tooling considerations has resulted in the poor performance of these systems and stressed for tool
scheduling [9]. In general, the objective of tool scheduling is to coordinate the flow of parts and tools to minimize unnecessary delays. Without an effective tool scheduling technique, the system may not operate as planned in the planning and part-scheduling stages [10]. It is shown that the added cost of tool automation can bring great improvements in economic efficiency [11]. Considering the above aspects, it is necessary to consider solution procedures for the part scheduling and tool allocation problems simultaneously. The concept of common tool magazine (CTM) that shares with and serves for several work centers reduce the cost of duplicating tools in each and every machining center is of particular interest in FMS systems. FMS scheduling problem is strongly non-deterministic polynomial-time (NP)-hard problem and is usually difficult to find its optimal solution. Direct and heuristic approaches are the two major methods used for resolving FMS scheduling problem. Many researchers have employed the direct approaches such as enumerative techniques, branch and bound techniques, and priority dispatching rules to solve various scheduling problems. The direct approaches do not fair-well over a broad spectrum of problem domains. Direct approaches are time consuming and also not able to produce quality solutions for larger-size problems. Therefore, effort has to be taken to search and develop of efficient heuristics to solve large-size problems. Nascimento [12] showed, with CPU time and solution quality, that the Giffler and Thompson algorithm [13], which was originally designed for the traditional job shop model, can still provide good results for an FMS Model. Tiwari et al. [14] proposed a GA based heuristic to solve machine loading problems in a FMS. Since the operations of a job are executed during a single machine visit, the problem is essentially an identical parallel machine problem with additional resources, since these problems are NP-hard even without additional resources, their solution calls for suitable heuristic approaches [15]. Prabaharan et al. [16] used two heuristics algorithms such as priority dispatching rule algorithm and simulated annealing algorithm for generating optimal schedules for a specific manufacturing environment by minimizing a makespan time. Jean-Paul Watson et al. [17] developed a model of problem difficulty for tabu search in the job shop-scheduling problem, borrowing from similar models developed for SAT and other NP-complete problems. Chao Yong Zhang et al. [18] developed a heuristics search approach combining simulated annealing and tabu search strategy for the job shopscheduling problem. Jerald et al. [19] used a particle swarm optimization algorithm in scheduling optimization of flexible manufacturing system. Sha et al. [20] modified the particle position representation, particle movement, and particle velocity to better suit PSO for the job shopscheduling problem and also applied tabu search to improve
Int J Adv Manuf Technol
the solution quality. Ali Husseinzadesh Kashan et al. [21] proposed a discrete PSO algorithm to tackle the problem of optimal assignment of jobs to machine to minimize the makespan time. Ant algorithms were proposed by Dorigo et al. [22] as a multi-agent approach to different combinatorial optimization problems. The ant colony optimization (ACO) algorithm performs better in problems such as the quadratic assignment problem [23], job shop-scheduling problem [24] and the vehicle-routing problem [25]. Blum et al. [26] proposed max–min ant system in the hyper-cube framework approach to tackle the broad class of group shop-scheduling problem instances. Ventresca et al. [27] presented an ant colony optimization algorithm approach to the job shopscheduling problem. Zhang et al. [28] presented an investigation into the use of an ACS to optimize the job shop-scheduling problem. T’kindt et al. [29] proposed an ant colony optimization algorithm to solve the two machine flow shop-scheduling problem with the objective of minimizing both the total completion time and the makespan criteria. Rajendran et al. [30] proposed an ant colony algorithm for permutation flow shop-scheduling problems with the objective of minimizing makespan followed by the consideration of total flow time of jobs. Rajendran et al. [31] proposed two ant colony algorithms to solve the problem of scheduling in flowshops with the objective of minimizing total flow time. Kuo-Ling Huang et al. [32] presented a hybrid algorithm combining ant colony optimization algorithm with the taboo search algorithm for the classical job shop-scheduling problem. In this research paper, an ant colony optimization algorithm is used for solving the scheduling problems attempted by the authors [16] and the results are found to be closer to the global optimum; in addition, less computational time is required. This paper is organized as follows: Section 3 includes the description of the scheduling problem. In Section 4, the elements of the Extended Giffler and Thompson (EGT) and ACO algorithm based on the scheduling problems are discussed. The computational results obtained by the application of this methods to the problems selected from the literature [16] are discussed in Section 5. Section 6 sums up conclusions.
3.1 Operating environment The work center of the FMS is capable of doing many operations and identical in nature. They can process a group of parts or part variety. The CTM has necessary tool varieties for all work centers and one tool in each variety. These tools are shared among the entire work center. The operating environment of FMS is shown in Fig. 1. The processing requirements of the jobs are: & & & Any job can be processed in any work center. Each job involves a set of operations and each operation requires a specific tool. Sequence of operations and respective tools vary from job to job.
3.2 Assumptions & & & & & & & & & The sequence of operations and its corresponding processing time and tools of the job are pre-specified. The operations of a job are executed during a single work center visit. Each work center/tool can process only one job at a time. Operation cannot be interrupted, i.e., each operation once started must be completed. A job does not visit the same work center twice. Availability of tools in each variety is considered as one, which can be used more than once of any job. The operation time of a job includes the loading, unloading, tool changeover, and setup times (both tool and job) along with processing time. Work center is capable of doing many operations. Once an operation is over, the tool returns to the common tool magazine with negligible transfer time immediately and is available for the next operation.
3.3 Objective The selection of performance measure purely depends on the type of manufacturing system, business environment,
“ k” Job “i” 1 i
1
....
k
K
3 Problem descriptions The usage of common tool storage is traditionally followed in many manufacturing systems with one tool grip serving many manufacturing facilities in order to reduce tool inventory. The description includes the operation environment, assumptions, objectives, and definition of the problem under consideration.
tik Tik
n
Fig. 1 Operating environment of FMS
Int J Adv Manuf Technol
and competition. As FMS requires very high investment cost, maximum hardware utilization is highly essential to have a competitive manufacturing cost. Considering this aspect, minimum makespan that increases the utilization of hardware is considered as the appropriate measure of system performance. 3.4 Problem definition “Generation of minimum makespanship schedule of ‘N’ different jobs which require processing on ‘m’ identical work centers with ‘T’ tools that are shared for many operations, in a flexible manufacturing system”.
START INPUT No. of jobs, Sequence of operations, Processing time, Tool No. Set Datum time (DT)
NO
Select the job = DT, Is there any tool conflict?
YES Resolve the conflict, arbitrarily select the job to be processed
Process the Job
4 Proposed methodologies
Update the job completion time for the processed job & all other operations of job accordingly
The general description of the proposed solution methodology that involves two stages is dealt. 4.1 Extended Giffler and Thompson algorithm The Giffler and Thompson proposed an algorithm to generate all feasible schedules for a pure job shop system. The GT algorithm is a numerical version of the procedure described for drawing a Gantt chart to arrive at an active feasible schedule. Using similar procedure, an EGT algorithm is proposed for the generation of active feasible schedules. Whenever two or more jobs require for the same tool at one time (conflict) the choice is made arbitrarily and an active feasible schedule is obtained. By enumerating all possible choices which occur at different stages one by one, the entire set of active feasible schedules can be obtained, including the optimal one. The optimal solution is obtained by evaluating the feasible schedules with the desired objective criterion. It shows that enumerating all possible combinations is a much more time consuming process and is highly complex for large problems. The procedural steps of EGT algorithm are explained in the following Section 4.1.1; the flowchart is shown in Fig. 2 and illustrated in Section 4.1.2. 4.1.1 Steps of an EGT algorithm Step 1: Construct a table subdivided into blocks one for each work center. Subdivide each work center block into columns, one column for each tool that requires processing on the work center. Step 2: Enter the first line of table, in the appropriate tool blocks, the processing time of the first operation of each job. The entries indicate the earliest possible completion time of immediate waiting operations of all jobs.
Are all the jobs are completed? YES STOP NO
Fig. 2 Flowchart for EGT algorithm for active feasible schedule generation
Step 3: Set the datum time equal to smallest of the entries and enter it on the appropriate column provided in the table on the same line. Step 4: Select the jobs whose operation time in the table matches with current datum time. Step 5: Check for tool conflict (more than one job waiting for the same tool)? If yes, go to step 6. If no conflict, go to step 7. Step 6: List all the jobs contend for the tool. Resolve conflict arbitrarily and select the job as the candidate for assignment with that tool under consideration and are earmarked. Step 7: The operation of the earmarked along with its processing machine and tool is assigned. Step 8: Update earliest possible completion time of immediate waiting operations including the next operation of the job just assigned in the next line of the table. Step 9: Check for the assignment of all operations. If ‘yes’ go to step 10. Otherwise, go to step 3. Step 10: End 4.1.2 Numerical illustration To illustrate the application of the EGT algorithm, the active feasible schedule generation for the three jobs, two
Int J Adv Manuf Technol Table 1 Component-operation matrix (problem no. 1) i k 1 Job allocation sequence: 2, 3, 1 (randomly taken). Tool allocation sequence: 2, 3, 1 (randomly taken) 1 2 3 32 63 91 2 81 42 53 3 73 81 62
work centers, and three operations problem no. 1 in the literature [16] is given in Table 1. The schedule generation procedure for the same problem is given in Table 2. 4.2 ACO algorithm ACO algorithms make use of simple agents called ants that iteratively construct candidate solution to a combinatorial optimization problem. The ant’s solution construction is guided by pheromone trails and problem-dependent heuristic information. In principle, ACO algorithms can be applied to any combinatorial optimization problem by defining solution components which the ants used to iteratively construct the candidate solutions and on which they may deposit pheromone. An individual ant constructs candidate solutions by starting with an empty solution and then iteratively adding solution components until a comTable 2 Schedule generation procedure Work center number 1 Tool number 1 2 3 0+6 *6 6+4 10 6+4 *10 10+8 18 10+8 *18 18+3 21 20+3 *23 23+8 *31 31+7 *38 2 Tool number 1 0+9 9 0+9 *9 9+5 14 9+5 *14 14+6 20 14+6 *20 2 3
plete candidate solution is generated. After the solution construction is completed, the ants give feedback on the solutions as they have constructed by depositing pheromone on solution components, which they have used in their solution. Typically, solution components which are part of better solution or are used by many ants will receive a higher amount of pheromone and, hence, will more likely be used by the ants in future iterations of the algorithm. Pheromone evaporation is the process by means of which the pheromone trail intensity on the components decreases over time. From a practical point of view, pheromone evaporation is needed to avoid a too rapid convergence of the algorithm towards a sub-optimal region. It implements a useful form of forgetting, favoring the exploration of new areas of the search space. The probability for choosing the next path by an ant will be directly proportional to the amount of pheromone on that path. State transition rule Starting from the initial node, each ant chooses the next node in its path according to the state transition rule [24] by using probability of transition. Let S be the set of nodes at a decision point i. The transition from the node i to a node k by an ant is calculated as given in Eq. 1. n o k Max Ci; ja h jb if q q0 1 j"S 0 otherwise
JP
DT
JC
FJ
Work center 1
Work center 2
2 2 2 2 2 1 1 1 1
3 3 3 3 3 3 – – –
6 9 10 14 18 20 23 31 38
2 3 2 3 2 1,3 1 1 2
21 31 22 32 23 33 11 12 13
*The operation of the earmarked along with its processing machine and tool is assigned
Int J Adv Manuf Technol
τ(i, j) is the quantity of the pheromone on the edge between the node i and the node j. η(j) is the heuristic information stored on the node j. α and β tune the relative importance in probability of the amount of the pheromone versus the operation time. q is a random number generated between 0 and 1 at each time of the selection of a node. q0 is a constant given as input within a range from 0 to 1 at the beginning of the algorithm. k is a random node selected according to Eq. 2
t i;k pi; k Pt i;jhkjb a h
j2S a b
START INPUT Job size, Processing time, Tool No., No. of iterations
INITIALIZE
tij = 0.1 eij= 0.1
Allocation of jobs to machines
if k"S otherwise
2
p ij =
0
Σ t ij
t ij
Global-updating rule Global updating is intended to reward edges belonging to the shortest path. Once all the ants have arrived at their destination, the amount of pheromone on the edge (i, j) belonging to the shortest path at a time t is modified by applying the global updating rule given in Eq. 3. t i; jt 1 rt i; jt1 Q=Lk 3
Sequencing of jobs
p ij =
Σ eij
eij
.
Calculate makespan time
ρ is the coefficient representing pheromone evaporation (note 0 < r < 1). Q is a constant whose value is chosen according to the size of the problem. Lk is the minimum tour length traveled by an ant among all the ants in the iteration. Local-updating rule The evaporation phase is substituted by a local-updating rule of the pheromone applied during the construction of the solution. The pheromone associated with an edge is modified each time the ant moves from node i to node j according to Eq. 4. t i; jt 1 rt i; jt1 r:t 0 4
NO Have all the ants have been generated? YES Get the solution of the best ant
C 0 is the initial pheromone value and is defined as C 0 =n/L, where L is the tour length produced by the execution of first iteration without pheromone information. The localupdating rule is equivalent to the trail evaporation in the real ants. The steps of ACO algorithm is shown as flowchart in Fig. 3. To determine the appropriate values of parameters in steps 2 and 11, a preliminary optimization phase was executed on 10 randomly chosen instances from the problem set in literature [16]. In each experiment, two of these three parameters were fixed, at values tij =0.1, eik = 0.1, q0 =0.9, and the effects of the unfixed parameter were analyzed at five levels (i.e., tij, eik, q0 {0.1, 0.3, 0.5, 0.7, 0.9}). Five trails were run for each instant and the best solution was selected. The computational results show that these parameters have a good performance at values around tij =0.1, eik =0.1 (in step 2), and q0 =0.9 (in step 11), which is therefore set in the experiments of the study. In particular, it is found that these chosen values of parameters were robust and largely independent of the problem.
Update the pheromone matrices
Check for termination
NO
YES Print the best sequence and its makespan time
STOP
Fig. 3 Flowchart for ACO algorithm
4.2.1 Steps of ACO algorithm Step 1: Input number of jobs, number of operations, processing time, tool number, and number of iterations. Step 2: Initialize pheromone level (tij and eik) as 0.1.
Int J Adv Manuf Technol
Step 3: Find the probability values (P11, P12 etc.,) using tij the formula pij P t and their cumulative
ij
5 Results and discussions One difficulty faced by researchers in scheduling is to compare their methodologies with those of other researchers. If the standard set of test problems is accessible, the performance of different algorithms can be compared on exactly the same set of test problems. For this reason, 20 problems are chosen from literature [16] as the test problems of this study. The performance of the ACO algorithm is predicted by comparing its results with the results obtained for the two algorithms used by Prabaharan et al. [16]. Results are summarized in Tables 3, 4, and 5 which shows the makespan time comparisons of proposed heuristics when m=2, m=3, and m =4 with different heuristics for the 20 problems and their computation experience is shown in Fig. 4. The percentage relative difference from best (PRDB) is used as the measure to compare the results presented here and those of other methods. PRDB PBEST SSOL =PBEST 100 5
Step 4: Step 5: Step 6: Step 7:
ranges for the first job. Generate a random number and find within which range the random number falls. Allocate that job to the corresponding machine. Repeat steps 3, 4, and 5 and allocate all the jobs to the available number of machines. Sequence the set of jobs allocated in each machine e using the formula pik Pike .
ik
Step 8: Calculate the makespan time using EGT algorithm for the sequence obtained. Step 9: Repeat steps 3–8 and calculate the makespan time for the given number of ants. Step 10: Pick the ant which has the lowest makespan time and its corresponding job sequence. Step 11: Update the pheromone values with the equation 1 tijnew tijold 0:9 Makespantime of the ant which yields minimum makespan time. Step 12: Repeat steps 3–10 up to specified number of iterations or a satisfactory predefined value for objective whichever occurs first. Step 13: Print the minimum makespan time and its corresponding sequence, the near-optimal solution.
Here, SSOL is the best solution found by the ACO algorithm and PBEST is the best-known solution by the other algorithms in the literature presented in this paper.
Table 3 Makespan time comparisons of proposed heuristics when m=2
Problem no.
No. of jobs
No. of operations
Best-known value (problem taken from literature [16]) 38a,b 99a 111a,b 131a 212a 300a 242a 402a 297a 257a 703a 542a 339a 332a 349a 399a 482a 532a 643a 797a
Proposed ACO algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 25 30
3 3 4 4 5 7 5 6 5 4 5 6 7 8 8 8 9 9 9 9
38 99 103 128 210 300 243c 394 294 265 693 540 340c 328 350c 419 476 527 643 813
Boldface are the minimum makespan time obtained for each problem from ACO algorithm
a Indicates best-known value from SAA b Indicates best-known value from PDRA c
Indicates near-optimal solution from ACO algorithm
Int J Adv Manuf Technol Table 4 Makespan time comparisons of proposed heuristics when m=3 Problem no. No. of jobs No. of operations Best-known value (problem taken from literature [16]) 25a,b 90b 83a,b 102a 168a 227a 200a 299a 220a 203b 540a 402a 247a 238a 253a 291a 344a 392a 450a 583a Proposed ACO algorithm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 25 30
3 3 4 4 5 7 5 6 5 4 5 6 7 8 8 8 9 9 9 9
25 91c 83 100 160 221 193 290 219 204c 524 403c 239 256 246 320 338 387 441 614
Boldface are the minimum makespan time obtained for each problem from ACO algorithm
a Indicates best-known value from SAA b Indicates best-known value from PDRA c
Indicates near-optimal solution from ACO algorithm
Table 5 Makespan time comparisons of proposed heuristics when m=4
Problem no.
No. of jobs
No. of operations
Best-known value (problem taken from literature [16]) – 87b 78b 90b 142a 192a 158a 270a 196a 187b 457a 328a 210a 200a 217b 247a 271a 322a 366a 464a
Proposed ACO algorithm – 87 79c 87 136 181 149 258 182 187 448 318 198 189 203 238 259 316 351 452
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 25 30
3 3 4 4 5 7 5 6 5 4 5 6 7 8 8 8 9 9 9 9
Boldface are the minimum makespan time obtained for each problem from ACO algorithm
Indicates best-known value from SAA
b Indicates best-known value from PDRA c a
Indicates near-optimal solution from ACO algorithm
Int J Adv Manuf Technol
Computational time in seconds 100 90 80 70 60 50 40 30 20 10 0
3 5 7 9 11 13 15 17 19
m=2 m=3 m=4
Number of Jobs
Fig. 4 Computational time experienced with ACO algorithm
performance of the proposed ACO algorithm is tested over 20 problems taken from the literature [16] and the results are compared to other heuristics such as priority dispatching rule algorithm and simulated annealing algorithm. The ACO algorithm provides the minimum makespan time with less computational time. The results reveal that the proposed ACO algorithm is found to be efficient, effective, and superior. This research work leads to a conclusion that the procedures developed in this work can be suitably modified to any kind of FMS and can be applied for optimizing different objectives separately as well as in combination. In the future, work availability and handling times of loading/unloading stations, robots, and AGVS can also be included.
The last column in the Tables 3, 4, and 5 shows the results obtained through the proposed ACO algorithm. The values in boldface are the better solution obtained for each problem. The proposed algorithm has obtained the better solution for the problems except problem number 10, 16, and 20 (from Table 3) and 14, 16, and 20 (from Table 4). The mean PRDB for the test problems are found to be 0.37% for m=2, 0.28% for m=3, and 3.61% for m=4. The ACO algorithm is able to provide better results than other approaches used in the literature [16]. It can also be seen in Tables 3, 4, and 5 that many new best solutions have been obtained in this technique. This makes it evident that ACO algorithm is an efficient method to solve FMS problems. The optimization procedure developed in this work is implemented using “C” language.
25
References
1. French S (1982) Sequencing and scheduling, 5th edn. Hardwood, London 2. Brucker P (1995) Scheduling algorithm, 1st edn. Springer, Berlin 3. Jawahar N, Aravindan P, Ponnambalam SG (1998) A genetic algorithm for scheduling flexible manufacturing systems. Int J Adv Manuf Technol 14:588–607 4. Mukhopadhyay SK, Nandi PK (1999) Solving tool allocation problem in flexible manufacturing system. J Ind Eng (India) 80:16–20 5. Rahimifard S, Newman ST (1997) Simultaneous scheduling of work pieces, fixtures and cutting tools with in FMCs. Int J Prod Res 35(9):2379–2396 6. Selim Akturk M, Siraceddin O (1999) Joint lot sizing and tool management in a CNC environment. Comput Ind Eng 40:61–74 7. Jun H-B, Kim Y-D, Suh H-W (1999) Heuristics for a tool provisioning problem in a flexible manufacturing system with an automatic tool transporter. IEEE Trans Robot Autom 15(3):488–496 8. Gray AE, Seidmann A, Stecke KE (1990) A synthesis of decision models for tool management in automated manufacturing. Manag Sci 39:249–567 9. Veeramani D, Upon DM, Barash MM (1992) Cutting-tool in computer integrated manufacturing. Int J Flex Manuf Syst 4:237– 265 10. Roh HK, Kim YD (1997) Due-date based loading and scheduling methods for a flexible manufacturing system with an automatic tool transporter. Int J Prod Res 35(11):2989–3003 11. Kahator SK, Leung LC (1994) Intermediate tool requirement planning for FMS. J Manuf Syst 13(1):9–19 12. Nascimento MA (1993) Giffler and Thompson algorithm for job shop scheduling is still good for flexible manufacturing systems. J Oper Res Soc 44(5):521–524 13. Giffler B, Thompson GL (1960) Algorithms for solving production scheduling problems. Int J Oper Res 8:487–503 14. Tiwari MK, Vidyarthi NK (2000) Solving machine loading problems in a flexible manufacturing system using a genetic algorithm based heuristic approach. Int J Prod Res 38(14):3357– 3384 15. Agnetis A, Alfieri A, Brandimarte P, Prinsecchi P (1997) Joint job/tool scheduling in a FMC with no on-board tool magazine. Comput Integr Manuf Syst 10(1):61–68 16. Prabaharan T, Nakkeeran PR, Jawahar N (2006) Sequencing and scheduling of job and tool in a flexible manufacturing cell. Int J Adv Manuf Technol 29(7–8):729–745
6 Conclusions The main aim of this research is to explore the potential of ACO algorithm for FMS-scheduling problems. It is based on imitation of the foraging behavior of real ants. A substance, pheromone, is deposited by natural ants after moving through a path. Ants move from one node to another node and progressively move towards the final node. The solution of the algorithm is a collective outcome of the solution found by all the ants. The pheromone trial is updated after all the ants have found out their respective solutions. The pheromone updating can be explored to enhance the capability of the proposed algorithm. The parameters of the state transition rule, determine the convergence rate of the algorithm as well as the quality of the obtained solution. To allow the algorithm to converge to a satisfactory solution, the evaporation constant has to be well tuned so as to guide the search into favored regions in the search space and at the same time prevent searching in small neighborhoods of local optima. Once the parameters are properly tuned, the algorithm converges satisfactory, thus accomplishing the stated goal of this work. The
Int J Adv Manuf Technol 17. Jean-Paul Watson J, Beck C, Howe AE, Darrell Whitley L (2003) Problem difficulty for tabu search in job-shop scheduling. Artif Intell 143(2):189–217 18. Zhang CY, Li PeiGen, Rao YunQing, Guan ZaiLin (2008) A very fast TS/SA algorithm for the job shop scheduling problem. Comput Oper Res 35(1):282–294 19. Jerald J, Asokan P, Prabaharan G, Saravanan R (2005) Scheduling optimization of flexible manufacturing systems using particle swarm optimization algorithm. Int J Adv Manuf 25:964–971 20. Sha DY, Hsu Cheng-Yu (2006) A hybrid particle swarm optimization for job shop scheduling problem. Comput Ind Eng 51(4):791–808 21. Kashan AH, Karimi B (2009) A discrete particle swarm optimization algorithm for scheduling parallel machines. Comput Ind Eng 59:216–233 22. Dorigo M, Gambardella LM (1997) Ant colonies for the travelling salesman problem. Bio Systems 43:73–81 23. Maniezzo V, Colorni A (1999) The ant systems applied to the quadratic assignment problem. IEEE trans Knowl Data Eng 11 (50):769–778 24. Colorni A, Dorigo M, Maniezzo V, Trubian M (1994) Ant system for job-shop scheduling. Belg J Oper Res, Stat Comput Sci 34:39–53 25. Bullnheimer B, Hartl RF, Strauss C (1998) Applying the ant system to the vehicle routing problem. In: Vo S, Martello S, Osman IH, Roucairol C (eds) Meta-heuristics: advances and trends in local search paradigms for optimization. Kluwer, Boston, pp 109–120 Blum C, Samples M (2004) An ant colony optimization algorithm for shop scheduling problems. J Math Model Algorithms 3:285– 308 Ventresca M, Ombuki BM (2004) Ant colony optimization for job shop scheduling problem. Tech Report #CS-04-04, Brock University, Canada Zhang J, Hu X, Tan X, Zhong JH, Huang Q (2006) Implementation of an ant colony optimization technique for job shop scheduling problem. Trans Inst Meas Control 28(1):93–108 T'kindt V, Monmarché N, Tercinet F, Laügt D (2002) An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. Eur J Oper Res 142:250–257 Rajendran C, Ziegler H (2004) Ant colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. Eur J Oper Res 155:426–438 Rajendran C, Ziegler H (2005) Two ant-colony algorithms for minimizing total flowtime in permutation flowshops. Comput Ind Eng 48:789–797 Huang K-L, Liao C-J (2008) Ant colony optimization combined with taboo search for the job shop scheduling problem. Comput Oper Res 35(4):1030–1046
26.
27.
28.
29.
30.
31.
32.