Job shop scheduling optimization through multiple independent particle swarms
The Authors
Gary G. Yen, School of Electrical and Computer Engineering, Oklahoma State University, Stillwater, Oklahoma, USA
Brian Ivers, School of Electrical and Computer Engineering, Oklahoma State University, Stillwater, Oklahoma, USA
Abstract
Purpose – The purpose of this paper is to develop an effective and efficient approach to exploit meta-heuristic in particle swarm optimization (PSO) for the job shop scheduling problem (JSP), a class of NP-hard optimization problems. The approach is to be built on a PSO with multiple independent swarms. PSO was inspired by bird flocking and animal social behaviors. The particles operate collectively like a swarm that flies through the hyperdimensional space to search for possible optimal solutions. The behavior of the particles is influenced by their tendency to learn from their personal past experience and from the success of their peers to adjust their flying speed and direction. Research in fusing the multiple-swarm concept into PSO is well-established in solving single objective optimization problems and multimodal problems.
Design/methodology/approach – This study examines the optimization of the JSP via a search space division scheme and use of the meta-heuristic method of PSO by assigning each machine in a JSP an independent swarm of particles. The use of multiple swarms in PSO is motivated by the idea of “divide and conquer” to reduce the computational complexity incurred through solving a NP-hard combinatorial optimization problem. The resulted design, JSP/PSO algorithm, fully exploits the computing power presented by the multiple-swarm PSO.
Findings – Simulation experiments show that the proposed JSP/PSO algorithm can effectively solve the JSP problems from small to median size. If certain mechanism of information sharing between swarms can be incorporated, it is believed that the new design could offer even more computing power to tackle the large-sized problems.
Originality/value – The proposed JSP/PSO algorithm is effective in solving JSPs. The proposed algorithm shows considerable promise when searching the space of non-delay schedules. It demands relatively lower number of function evaluations compared to other state-of-the-art. The drawback to the JSP/PSO is that the GT scheduling adopted is too computationally expensive. Future works will address this concern.
Article Type:
Research paper
Keyword(s):
Job sequence loading; Production scheduling.
Journal:
International Journal of Intelligent Computing and Cybernetics
Volume:
2
Number:
1
Year:
2009
pp:
5-33
Copyright ©
Emerald Group Publishing Limited
ISSN:
1756-378X
1 Introduction
For several decades now, much research has been conducted into the field of evolutionary computation, or meta-heuristic search techniques. These techniques are preferred for many optimization problems where the search space is either very complex or very large. One of the ways researchers can measure the effectiveness of their designs is to test them on known optimization problems, such as the job shop scheduling problem (JSP). Not only does the JSP serve as a benchmark to judge the quality of various algorithms by, but also as a model for which the field of scheduling theory can be advanced. Scheduling theory is studied by researchers in many fields and a direct application to today's industry. For example, consider the many postal or parcel services operating throughout the world, or air traffic control centers directing thousands and thousands of planes to safe ground. Essentially, the efficient use of time means lower costs and higher profits.
Our ability to produce optimal schedules has not necessarily progressed with the advance in technology and processing power over the years. The amazing processing power of modern computers has definitely helped researches evaluate many different methods of scheduling at fast speeds, but in terms of finding a technique that consistently produces optimal schedules for many different sizes of problems has not yet been fully matured. Even the modern computer is hardly a match for the enormous combinatorial complexity of a medium scale JSP. The JSP belongs to the class of NP-hard. NP-hard problems have an exponentially growing search space as the problem increases in dimension. For example, the search space (possible schedules) for a JSP that consists of ten jobs to be processed on ten machines is (10!)10. Which is equal to approximately 3.9594 × 1065. Even though not all of these solutions are feasible, with this information we can see how even modern processors are hardly a match for this kind of combinatorial space. Therefore, methods and heuristics must be developed to provide good search directions within this space for our modern computers to perform their calculations. This is where the field of computational intelligence holds much promise. Where exact methods of optimization search out the best solution exhaustively by using mathematical formulations, methods of computational intelligence rely on certain heuristic principles or biologically motivated ideas to explore and then converge to the best found solution.
A lot of research pertaining to optimization of the JSP in recent years has focused on many meta-heuristic methods (Dimopoulos and Zalzala, 2000). Most of this research implements the genetic algorithm, an algorithm that is modeled after evolution and the “survival of the fittest” principle. According to Jain and Meeran (1999), this evolutionary computation algorithm has had success with the JSP, it has not proven itself yet to be a superior method when compared to other computational intelligent techniques. One branch of computational intelligence which has shown promise in solving other optimization problems is particle swarm optimization (PSO). The PSO algorithm was originally modeled after the behavior of a flock of birds in flight. It is currently considered one of the fastest converging techniques of computational intelligence, and a well-suited algorithm for multimodal functions (Song and Gu, 2004). As of yet, particle swarm behavior has not been solely applied to the traditional JSP. This could because of the fact that the PSO algorithm does not lend itself inherently to the optimization of permutations, which are often use to indirectly represent solutions to the JSP. Although, the PSO optimization technique has been applied to other scheduling problems, such as the flow shop scheduling problem (FSP), the flexible job shop scheduling problem (FJSP) and others (Lian et al., 2005; Tasgetiren et al., 2004a, b; Xia and Wu, 2005). Given the success of this optimization strategy in other areas, and the ever present need for better heuristic methods for solving JSP, it is only fitting to try and make this connection of the PSO to the JSP, especially due to the fact that constructing a feasible schedule can be very computationally expensive. This connection is not necessarily straight forward, because of the previously mentioned obstacle regarding the continuity nature of the PSO and the permutation nature of an indirectly represented JSP solution. Therefore, a unique approach has been developed to make this optimization possible. This approach involves assigning each machine defined in a particular JSP its own independent particle swarm. As will be explained later, this multiple swarm method will allow for a smaller search space than that of the more obvious solution representation of permutation with repetition. In fact, it is the unique nature of the PSO algorithm lends this proposed search space division scheme feasible.
The remainder of this paper is organized as follows: the JSP is introduced in Section 2, and prior work is reviewed in Section 3. In Section 4, PSO is briefly overviewed. Section 5 elaborates the details of the proposed algorithm, the JSP/PSO, while Section 6 consists of the results from the numerical study. Finally, in Section 7 conclusions are drawn.
2 The job shop scheduling problem
The JSP is one of many types of scheduling problems that researchers from many fields are currently attempting to solve optimally using various meta-heuristic ideas. The solution to these scheduling problems is simply the determination of the optimal assignment of a finite number of resources to a finite number of operations, while adhering to many pre-defined constraints, usually precedent constraints. Precedent constraints, or technological constraints, dictate the order of operations for each job, or the order of machines a job must visit. A solution to a JSP is a schedule specifying when each machine is to start processing certain operations that does not violate any precedent constraints. The ultimate goal is to minimize the makespan of the problem, or the minimum time required for all jobs to finish processing. In the following, the JSP is defined, and then descriptions of the different types of schedules that can be constructed are explained.
A (n×m) JSP is defined by a specific number of jobs, n, each consisting of an order of operations, m , which are equal to the number of machines or resources specified in the problem. So a job, J i is a pre-defined order of operations O i =(O i1,O i2, … ,O im ). Each operation O ij has a processing time, or job duration, τ ij . For the traditional JSP, the following rules apply:
- each job must be processed by each machine in a certain order;
- each machine can only process one job at a time;
- each job can only be processed by one machine at a time;
- each job must be processed by each machine exactly once; and
- no preemption is allowed, or once a job has started processing it cannot be interrupted.
The specific order of operations, or the order of machines that a job must visit, are the precedent constraints, or the technological constraints for that job. These precedent constraints impose the JSP its difficulty. An example of a (10 × 10) JSP, the famous MT10 problem is shown in Table I (Muth and Thompson, 1963).
Here, each row is a job sequence J i with processing time τ ij in parentheses. There are ten rows, which mean there are ten jobs, and there are ten columns which mean there are ten machines. Each row is a permutation of numbers representing the sequence of machines that job must visit. For example, Job 3 must go to Machine 1 first for 91 time units, then it must be processed on Machine 0 for 85 time units, then go to Machine 3 for 39 time units and so on.
2.1 Related scheduling problems
The traditional JSP has many “cousins,” or other scheduling problems with the same goal, to produce an optimal schedule of a number of jobs through a number of machines. The nature of the specified constraints, the number of resources available, and the number of jobs are what differentiate one “shop” scheduling problem from the other. In the following, some of the other scheduling problems are briefly explained to distinguish the traditional JSP, to add perspective on the scope of scheduling problems in general.
2.1.1 The flexible job shop scheduling problem
Another scheduling problem that proves itself to be computationally hard is the FJSP. In the FJSP, an operation of a given job can be processed by multiple machines. So each operation O ij has a pre-defined list of machines that are capable of performing that operation. A FJSP with “total flexibility” means that any operation can be processed by any machine. However, the processing times by each machine for a given operation are all different, which lends to the need for optimization. Most FJSP problems are optimized in two steps, first the optimal assignment of each operation to a machine is made, then the optimal schedule is determined. The FJSP has an even bigger computational space than the JSP, and in fact the JSP can be considered a general case of the FJSP.
2.1.2 The flow shop scheduling problem
The FSP is another n job by m machine scheduling problem. The FSP differs from the JSP in that each job j has the same order of operations, or precedent constraints. The goal is to determine the optimal order of operations that all jobs will share that will minimize the makespan.
2.1.3 The single machine weighted tardiness problem
In the single machine weighted tardiness problem (SMWTP), there is only one single machine and a list of operations to be processed on that machine. At first thought, this does not seem to pose an extraordinary scheduling problem, because with only one machine the makespan, or total completion time, of any permutation of jobs will be the same. However, the problem's difficulty comes into play with the addition of due dates and weights for each job, parameters not defined for the other scheduling problems in a non-dynamic environment. The goal becomes to find the optimal order of operations not to minimize the makespan, but to minimize the total-weighted tardiness. In the SMWTP, the tardiness of each job is multiplied by its weight, and the summation of this weighted tardiness is the final cost value of the schedule. Suddenly, with the addition of weighted tardiness and due dates, this problem becomes a scheduling problem of great complexity like its other cousin scheduling problems, especially for problems with 50 or more operations each with different weights.
2.2 Types of schedules
As stated before, a solution to a JSP is in essence a schedule of operations, or a set of starting times for each operation, which does not violate any of the imposed constraints. It turns out that schedules can be classified into different categories depending upon how the sequencing of operations affects the makespan of the problem.
2.2.1 Semi-active schedules
Semi-active schedules are schedules in which the next operation in a technological sequence is scheduled at the earliest allowable time. In semi-active schedules, no operation can be started earlier without changing the operating sequence of any machine. Changing the operating sequence of a machine will not necessarily violate precedent constraints. The fact that they will be scheduled at the earliest allowable time makes it a semi-active schedule. To understand this concept, it is easier to show visually what a semi-active schedule is NOT. Consider the following simple JSP problem as shown in Table II.
Figure 1 is a Gantt chart of one possible non-semi-active schedule for this simple (3 × 3) JSP. Notice how the second and third operations on Machine 1 are not scheduled at the earliest allowable time. The red boxes mark this unnecessary delay. Obviously, schedules that are not semi-active are not optimal. To make this schedule semi-active the second and third operations on Machine 1 can simply be moved left to the earliest allowable time. Figure 2 shows this new semi-active schedule. Notice that no operation can be started earlier without altering the operating sequence of any machine.
2.2.2 Active schedules
These are schedules in which no operation can be started earlier without violating a precedent constraint, or increasing the total processing time of any machine. The schedule in Figure 2 is semi-active, which means no operation can be started earlier without altering the operating sequence of any machine. However, if we were to alter the operating sequence of any machine, an active schedule could be produced. Semi-active schedules in general are not optimal. Optimal schedules lie in the space of active schedules. It is possible to alter the operating sequence of the machines to produce a schedule with a smaller makespan and preserve the precedent constraints of the problem. To turn a semi-active schedule into an active one, permissible left shifts are made. Permissible left shifting simply means switching the operating sequence of two adjacent operations as long as it does not violate any precedent constraint or cause a delay in any of the machine sequences. When all permissible left shifts are made to a semi-active schedule an active schedule is thereby obtained. This method is useful in turning an already existing semi-active schedule into an active schedule. The following figures demonstrate this left shifting procedure.
In Figure 3, the first two operations in Machine 3's operating sequence are switched, or left shifted. This move does not violate any of the precedent constraints of the problem and does not delay any machines sequence. This left shift may seem pointless, because the overall makespan of the problem did not decrease. However, it allows us to do the next left shift shown in Figure 4.
This time the first two operations in Machine 2's sequence were shifted and scheduled at the earliest allowable time. Figure 5 shows the final active schedule. Note the drastic improvement of the makespan obtained by permissible left shifting. This is an active schedule because there are no more permissible left shifts without violating a precedent constraint. For a simple (3 × 3) JSP, one might mistakenly think that there is only one active schedule and it is optimal. However, this is not the case. Many more active schedules could be generated for this problem, but obviously not all of them can be optimal. The schedule above may or may not be optimal. Keep in mind the enormous combinatorial space of the JSP as mentioned in the Introduction. For this (3 × 3) problem, there are (3!)3=196 possible schedules. Granted, many of these schedules are infeasible, but depending upon how an optimization algorithm works those infeasible schedules are still in the search space, which adds complexity.
2.2.3 Non-delay schedules
These are schedules in which no machine is kept idle while it could be processing an operation. The active schedule in Figure 5 is also happens to be a non-delay schedule as well. The instant an operation becomes available for a machine then it is scheduled without unnecessary delay. It might be tempting to think of optimal schedules as non-delay schedules, however this is not always true. Often holding a machine idle for a period of time so that more jobs become available for processing (meaning they get done processing on other machines), and then scheduling one of these newly available jobs can lend to optimal schedules. This is best illustrated with an example. In Figure 6, another possible Gantt chart is shown of the JSP with a single change. The processing time of the first operation in Job 2 has been increased to make this point. Clearly, this an active non-delay schedule, since no machine is kept idle when it could be processing a job.
This schedule is a non-delay schedule, however, it is not optimal. Notice when Job 1 is done processing on Machine 2 it is immediately scheduled on Machine 3 (because it is the first job to become available for that machine). Also notice how Job 2 on Machine 1 finishes not too long after the previously mentioned event. Now, notice how the next operation for Job 2 also happens to be for Machine 3. The point is both of these operations require Machine 3 within a relatively small amount of time. With non-delay schedule building, Job 1 is immediately processed first. It turns out it might be better to delay processing on Machine 3 and process Job 2 instead of Job 1 first. This idea is shown with the schedule in Figure 7.
The red box indicates the idle delay time for Machine 3. This delay and the resulting processing of Job 2 before Job 1 on Machine 3 produced a more optimal solution. This is why we can safely limit our search to the set of active schedules, but not necessarily the set of non-delay schedules. This schedule is both active and semi-active, and should not be confused with a non-semi-active schedule. A schedule that is not semi-active holds machines idle for no benefit.
2.3 Representation of schedules
2.3.1 Direct representation
Direct representation of a schedule is any form of representation that directly specifies when all the operations are to begin processing on the machines. Optimization occurs directly in the schedule space. An example would be to create (n×m) set of starting times for a (n×m) JSP and optimize those values directly, based on the makespan they produce. This type of relationship could be well-suited for meta-heuristic optimization since a meta-heuristic algorithm learns or evolves a set of starting times, simply based on an objective value, such as the makespan. It is fairly obvious to realize that using direct representation would result in infeasible schedules, because the precedent constraints of the problem would likely be violated. Therefore, if direct representation is implemented, extra steps must be added for feasible optimization to take place. Either infeasible schedules should simply be removed from the population, or repair procedures should be performed to transform infeasible schedules to feasible ones. Direct representation is advantageous because of its simplicity and speed, but not good because of its indiscriminate search of both feasible and infeasible schedules. Indirect representation has the opposite characteristics.
2.3.2 Indirect representation and scheduling algorithms
One common way to avoid violating precedent constraints is to represent a JSP schedule in an indirect fashion and use a scheduling algorithm to transform the indirect representation into a feasible schedule. The scheduling algorithm consults the precedent constraints of the problem and uses the indirect representation of the problem to make decisions that ensure the generation of a feasible schedule. This is advantageous because the optimization operators can operate without venturing into infeasible space. These scheduling algorithms can range from very simple to very complex, and can produce schedules anywhere from semi-active to non-delay. The more restrictive the search of the schedule space, the more complicated the scheduling algorithm becomes to produce those schedules.
2.3.3 Permutation with repetition
An example of an indirect representation is permutation with repetition originally proposed in Bierwirth (1995). In this representation, a permutation of job numbers (n×m) long is decoded into a feasible schedule by a scheduling algorithm. Each number represents a job, and that number is repeated m times. The kth repetition of job j represents the kth operation to be processed for job j. This scheduling algorithm builds semi-active schedules by default, which include the class of active and non-delay schedules.
It is easy to understand by using an indirect representation with a corresponding scheduling algorithm, it is possible to ignore precedent constraints when searching in the decision space. This is because a scheduling algorithm will consult the precedent constraints before scheduling. Permutation with repetition is a simple and effective scheduling algorithm. The main benefit of using this representation is that the corresponding scheduling algorithm is very fast and simple, and therefore not computationally expensive. This makes sense, because to build semi-active schedules operations are simply scheduled at the earliest starting time, which is easily done when decoding a schedule represented by a permutation. Limiting your search space to active schedules usually involves a scheduling algorithm that looks ahead in time, which adds computational time and complexity. The GT algorithm is an example of this, which can be used with another indirectly represented solution, priority lists.
2.3.4 The GT scheduling algorithm
As mentioned before, the type of schedule produced as a result of a scheduling algorithm very much depends upon the complexity of the scheduling algorithm. A scheduling algorithm that simply schedules operations as early as possible is liable to produce semi-active schedules, which include non-optimal schedules. However, an algorithm that “looks ahead into the future” might produce active schedules. Since, all optimal schedules are active schedules it would be beneficial to limit our search to the set of active schedules. The GT algorithm does just this. It is one of the most cited scheduling algorithms by far, and was developed in Giffler and Thompson (1960) and has been used ever since (Lian et al., 2005). The algorithm is outlined:
The GT algorithm:
- Let D be a set of all earliest schedulable operations in all job sequences not yet scheduled.
- Let operation, O jr , be the operation with the earliest completion time, EC, in set D. O jr =min{O−D|EC(O)}, where j is the job and r denotes the machine.
- Develop a conflict set for machine M r consisting of all operations that will require machine r before operation O jr will be completed. ES – earliest starting time. ES(O kr )<EC(O jr ).
- Select an operation out of the conflict set, and schedule it on M r .
Basically, the algorithm builds a schedule one operation at a time. First, it selects a machine by determining which unscheduled operation has the earliest completion time, EC, and what machine it requires to be processed on, r. It then looks ahead for operations that will be available to start processing on r before time EC, and places these operations in a conflict set. It is called a conflict set because they all have an “equal right” to be processed on machine r during the considered time EC. By default, the GT algorithm searches active schedule space. However, one of the great aspects of this algorithm is that if the algorithm can be used to build only non-delay schedules by making EC equal to zero. This means conflict sets will only be constructed from operations that are already available for machine r, not any that will become available. This should agree with what has been explained about non-delay schedules previously. In fact, we can search the space of parameterized active schedules, by making EC a value between 0 and EC. This idea is explored in more detail in Section 6.
Once the conflict set has been generated which may consist of one or more operations, an operation must be selected and scheduled. The GT algorithm does not specify how to make this selection; an active schedule will be built regardless. However, an optimal schedule will require the right selections out of the conflict sets generated throughout the schedule building process. This is where the priority list can come into play with the GT algorithm. In a priority list representation each machine has its own priority, or order of jobs, that it prefers to process. This gives a combinatorial space of (n!) m . For a (10 × 10) JSP, this is equal to (10!)10≅ 3.9594×1065. This is 5.9531 × 1026 smaller than the search space of permutation with repetition. This reduction in search space should make optimization easier when the appropriate scheduling algorithm is used to decode the priority list. The proposed JSP/PSO algorithm uses the GT algorithm in conjunction with priority list for this reduced search space trait.
3 Literature survey
One of the most well-known and defining works in scheduling theory was published in the early 1960s. Giffler and Thompson's (1960) “Algorithms for solving production scheduling problems” introduced the most famous and widely used scheduling algorithm, called the GT algorithm. The GT algorithm insures the construction of an active schedule. Three years later “Industrial scheduling” by Muth and Thompson (1963) was published which introduced the first famous job shop scheduling benchmark problem, a (10 × 10) problem that took 20 years to solve exactly. Since then researchers have applied many deterministic algorithms to the JSP, and more recently the use of heuristics and evolutionary techniques. In “A state-of-the-art review of job-shop,” Jain and Meeran (1999) divide the approaches to the solving this huge combinatorial problem into two main techniques, exact and approximate.
Exact methods use mathematical formulations to arrive exactly at the optimal solution. Since, the problem space of the JSP problem is so large, these exact methods are not useful for anything but problems of small dimension. This is why the MT10 problem, a (10 × 10) JSP introduced in 1963 took 20 years to solve exactly. Approximate methods, on the other hand, exploit any heuristic knowledge to search for the optimal solution in a stochastic sense. Approximate methods have the ability to explore the solution space quickly and arrive at a near optimal solution in a directed stochastic manner. Approximate methods hold the key to generating the best schedules of problems of order (10 × 10) or higher. Because of the exponentially growing search space of the JSP, to exhaustively and exactly determine the optimal solutions for JSPs with order higher than (10 × 10) can be too time consuming, even with modern computers. This was especially true back in the 1950s and 1960s when today's computing power was not available. To address this concern, engineers, scientists and production managers relied on heuristics to help them produce a near optimal schedule. These heuristics normally took the form of dispatching rules.
Dispatching rules are another way to indirectly determine the schedule of a particular JSP. Dispatching rules are commonly used in conjunction with the GT algorithm. Recall that the GT algorithm must select operations from a conflict set. This is where dispatching rules come into play. Dispatching rules are heuristic guidelines that dictate which jobs should be selected out of a conflict set according to some measurable standard, such as “shortest processing time.” Developing good dispatching rules is where a lot of heuristics come into play in the JSP. Obviously, one can surmise that there might exist intuitive ways of assigning priority to operations so as to generate a schedule with near optimal makespan. Before the processing power of modern computers, a lot of focus was given to the development of dispatching rules. In fact there are hundreds of dispatching rules that have been tested through the years, starting in the 1950s and 1960s when Jackson (1955, 1957), Smith (1956) and Rowe and Jackson (1956) constructed the earliest work on dispatch rules. Recently, in Chang et al. (1996), the authors composed a survey on many dispatching rules and compared them to each other. The most popular ones were summarized in a table by Jain and Meeran (1999).
Meta heuristic techniques can be classified as local search techniques because of the way they search and solve problems. Meta-heuristic techniques all start at a certain initial solution, or group of solutions, and will iteratively arrive at a near optimal solution by making small or local changes in the problem space. Most research of meta-heuristic techniques and scheduling problems have focused on using the genetic algorithm, although simulated annealing (SA), Tabu search (TS), PSO and ant colony optimization have been applied as well. Like dispatching rules, priority lists are another heuristic way of selecting an operation out of a conflict set. Each machine is assigned a processing priority of the jobs in the JSP. Operations are selected out of conflict sets by referencing the machines processing priority for the jobs in the conflict set. Each machine's priority list can then be optimized by determining the best permutation of job numbers or best permutation of the priority list. Therefore, this indirect representation method lends itself much more conducive to meta-heuristic optimization than using dispatching rules. In Davis (1985), he was the first to apply an evolutionary algorithm in an effort to solve the JSP. He used a genetic algorithm to evolve a priority list for each machine. An example of a priority list for a (5 × 5) problem is given in Table III.
This use of priority lists, by Davis, is what first opened the door to the application of meta-heuristic methods of solving the JSP. By evolving a priority list, Davis was able to ignore the precedent constraints of the problem, which makes using a genetic algorithm much easier. It should be noted that even though varying a machines priority list will indirectly affect the schedule of a specific JSP, it will not always produce a unique schedule. More than one priority list can easily generate the same schedule. This can make the optimization process more difficult. Since Davis's work, a large amount of research has been conducted into the application of the many meta-heuristic techniques to the JSP. Most of the research has been focused on the genetic algorithm, although some consider the GA an ineffective way to solve the JSP. When compared to SA, TS, the GA seems to perform the poorest according to a comparative study done by Pirlot (1996).
As of yet, PSO has not been applied to the traditional JSP, with one exception. Xia et al. (2004) applied a hybrid SA/PSO to the traditional JSP. In their study, SA was used to fine tune solutions found by the PSO algorithm. The results of this hybrid algorithm were promising. Many of the most widely used JSP benchmark problems were solved to optimal or best known solutions. This means that the implementation of a pure PSO algorithm might very well be an efficient and effective way of solving these types of huge combinatorial optimization problems without using SA for fine tuning.
However, there is few literature published on the application of the PSO algorithm to some of the other scheduling problems, such as the permutation flow shop problem (PFSP) also called the flow shop scheduling problem (FSSP), or the SMWTP. Tasgetiren et al. (2004b) applied PSO to the SMWTP. They developed the smallest value position (SVP) rule in order to transform the continuous space of the PSO to the permutation space used to represent a solution of the SMWTP problem. Tasgetiren also published a paper on the PSO applied to the permutation flow shop sequencing problem (Tasgetiren et al., 2004a). The same SVP rule was used for the necessary space transformation from continuous to permutation space. This space transformation concept was used for the traveling salesman problem by (Pang et al., 2004). Their method of space transformation was called the greatest value priority (GVP) rule. Using PSO and local search techniques they were able to solve medium scale (50-75 city) TSP problems.
PSO has also been applied to the FJSP in Xia and Wu (2005) recently. The FJSP is another scheduling problem related to the JSP. They used the PSO not to determine the schedule, but to assign each operation to a machine as is required for the FJSP. Instead of using a GVP or SVP rule, Xia and Wu simply limited the search space of the PSO to the value of the highest number in the permutation and simply rounded-off any decimal values created from the PSO equations to get an integer value. This integer value then represented a particular machine in the problem at hand. So, the PSO in not necessarily new to the area of scheduling problems, just the traditional JSP.
Not all researchers have used this particular space transformation technique to apply the PSO in permutation problems. Wang et al. (2003) developed a way to represent the difference in two permutations as a function of swap operators (SO). These SO perform a switch on two numbers in a permutation, and multiple SO in a given order form a swap sequence (SS). A SS can, therefore, actually represent the difference between permutations. The authors then defined mathematical operations for the SS so that the traditional PSO velocity and position equations could be applied to an actual permutation. The velocity and position equations for PSO are discussed in Section 4 of this paper. The authors' methods were applied to a simple 14-city TSP and were able to achieve the optimal solution. This achievement demonstrated the success of their method, however harder and larger TSP problems were not tested. Lian et al. (2005) developed a similar particle swarm optimization algorithm and applied it to the FSP (FSSP or PFSP). These researchers, like Pang et al. (2004) developed a way for the PSO algorithms to operate directly in the space of permutation problems. Their PSO algorithm is called “similar” because they used crossover and mutation techniques, easily performed on permutations, but originally developed for the genetic algorithms. Their crossover and mutation operations were used to update the velocity and position of the particles in the PSO-like algorithm.
Many of the meta-heuristic techniques used to solve sequencing problems like the TSP, FSSP, SMWTP, FJSP and others, can also be adapted to solve the JSP since both solutions can be represented by a permutations of numbers. However, the JSP and FJSP are unique because their solution must be a permutation for every machine in the problem. In other words, there must be a set of permutations – one for each machine in the problem. Therefore, some extra steps might have to be implemented in the encoding and decoding process of the permutations.
4 Particle swarm optimization
PSO falls under the category of swarm intelligence. Swarm intelligence is an optimization strategy that draws upon the knowledge of many agents interacting locally in an environment to find a global solution for a given problem. There is no global control of these agents and they interact randomly and share information about their environment with one another. In the physical world, flocks of birds, schools of fish, and ant colonies are examples of this behavior. In 1995, Kennedy, a Social Psychologist, and Eberhart, an Electrical Engineer, first applied swarm intelligence behavior to the search space of optimization problems (Eberhard and Kennedy, 1995). They were inspired by a computer simulation of a flock of birds developed in 1990 by Heppner and Grenander. Their concept was to give each particle a social component and an individual component. Individual particles' behaviors would be influenced by their best positions and by the best position found by all particles in the swarm. The particles search a N dimensional problem space by “moving through it” with a certain velocity. Each position a particle has in this space represents a possible solution to the objective function. The particles in a traditional PSO algorithm are governed by the following equations: Equation 1 where n is the dimension, i is the particle number and t is the iteration. Each particle i remembers its velocity V i , its position X i , its previous best position pBEST i as determined by the objective value produced by that position, and the best position obtained by any particle in the swarm gBEST. The coefficients c 1 and c 2 are acceleration constants for the personal and global components, respectively, r 1 and r 2 are random numbers generated uniformly between [0, 1], which add the necessary stochastic quality of such meta-heuristic optimization methods. The inertial component w controls the impact of the particles previous velocity. The right selection of w will insure that a particle's velocity does not blow up over time. In fact, it is usually desirable to need a particle's velocity to slow down over time, and thereby become more precise and converge to the best found solution. It is also common to vary w with the iterations. The two acceleration constants, c 1 and c 2, can also be varied with the iterations. The relationships between these two constants at any given iteration will put either an emphasis on local exploitation, global exploration, or both. The random numbers r 1 and r 2 add the necessary stochastic quality that will ensure decent exploration of the search space. As will be shown later, the JSP/PSO cycles the values of these constants over time.
5 The JSP/PSO design
Since the conception of this optimization strategy, the PSO algorithm has been applied to many optimization problems. However, PSO in its purest form is not well-suited for searching the permutation space of numbers. The particles in the PSO algorithm are designed to explore continuous space. Therefore, extra steps must be taken to adapt the PSO algorithm to permutation space. The proposed JSP/PSO algorithm will evolve a set of permutations to indirectly represent a solution to a JSP. There are two obstacles that will prevent use of the PSO to the JSP. One obstacle is that a permutation of numbers which can represent a solution to the JSP (in the context of a scheduling algorithm) cannot be optimized directly with the PSO governing equations. There has to be a way to transform the continuous space into permutation space. The other obstacle is deciding how to transform this permutation(s) of numbers into a schedule, or in other words deciding what kind of scheduling algorithm will be implemented. These two distinct processes are shown in Figure 8. In the following, we will discuss in detail how these two previously mentioned “obstacles” are addressed in the proposed JSP/PSO algorithm.
5.1 From continuous space to permutation space
In order to transform the continuous space of the particles into permutation space the GVP rule (Pang et al., 2004) was implemented. The GVP rule is simply the assignment of each dimension or component of a particle in continuous space an integer index. The sequence of these assignments put together make up the permutation. So, if there are n dimensions in continuous PSO space, the permutation will be n values long. To determine the permutation a particle represents, the dimension that has the greatest magnitude is given a 1 value. Then the dimension of the particle that has the next greatest magnitude is assigned a value of 2. This process is repeated for all dimensions of the problem. In Figure 9, a particle in 3D space is transformed into a permutation using the procedure. This permutation of three numbers could easily represent processing priority for a machine in a JSP with three jobs. Obviously, for a JSP with n jobs, a particle with n dimensions in continuous space could be used to determine a single machine's schedule in a JSP. This is how the GVP rule works.
5.2 From a permutation to a schedule
The next obstacle has to do with how exactly the schedule will be represented by permutation of numbers, which now can be optimized by the PSO. This process is shown in green in Figure 8. This section will address this issue specifically. The advantages and disadvantages of two representation methods will be discussed, permutation with repetition and priority list representation. The JSP/PSO algorithm was influenced by both of these representation methods.
5.2.1 Permutation with repetition representation
Permutation with repetition represents a job shop schedule by using the job number in a sequence that is (n×m) long. Each job number is repeated m times, or the number of machines there are in the JSP. Since each job has a certain technological sequence, or processing order, each instance of the job number in the sequence represents the next operation to be processed in that technological sequence. By using a scheduling algorithm that simply schedules operations specified by the permutation as early as possible, a semi-active schedule can be generated. This process is shown in Table IV and Figure 10 for convenience.
This is an easy way to represent and decode a schedule. However, there are a couple of drawbacks. One drawback is the fact that this procedure is not guaranteed to produce an active schedule. It is only guaranteed to produce a semi-active schedule, which contains the classes of active and non-delay schedules. It is obvious that the schedule in the example above is not an active schedule, rather semi-active. By simple left shifting the 3rd operation on Machine 2 with the one before it, a schedule with a shorter makespan is produced. The other drawback is that many of the same permutations will produce the same schedule. For example, the last two job numbers could be switched in the above permutation and the same schedule will result. This is because both of those job numbers are representing operations that require different machines. The lack of one to one matching is not a surprise when considering that the space of permutations with repetition is much greater than the number of possible semi-active schedules, feasible or infeasible. In fact the permutation space of n numbers is n!. However, if the any of the numbers in the permutation repeat the search space is reduced by a factor of the repetition number factorialized. So, for a particle to represent a schedule in permutation with repetition form, the particle will have to have n×m dimensions, which will consist of n numbers that each repeat m times. Which in turn means that the search space for a particle becomes (n×m)!/(m!) n . For example, a (10 × 10) JSP has a combinatorial search space of 2.357 × 1092. This is huge, to say the least. This method seems like overkill especially when many of the permutations will also result in the same schedule, and many will result in semi-active schedules as well. However, the benefits of using permutation with repetition might out weigh these drawbacks. The main benefit of using this representation is that the corresponding scheduling algorithm is very fast and simple, and therefore not computationally expensive. This makes sense, because to build semi-active schedules operations are simply scheduled at the earliest starting time, which is easily done when decoding a schedule represented by a permutation. Limiting your search space to active schedules usually involves a scheduling algorithm that looks ahead in time, which adds computational time and complexity. The GT algorithm is a good example of this, which can be used with priority lists.
5.2.2 Priority list representation
It is actually possible to reduce the size of the search space by using a priority list for each machine instead of an n×m set of numbers. In a priority list representation each machine has its own priority of jobs that it prefers to process of length n. This gives a combinatorial space of (n!) m . For a (10 × 10) JSP, this is equal to 3.9594 × 1065. This is 5.9531 × 1026 smaller than the search space of permutation with repetition. This reduction in search space should be helpful when the appropriate scheduling algorithm is used to decode each machines priority list into a schedule. The scheduling algorithm usually used with a priority list is the GT algorithm. By using the GT algorithm, it is guaranteed to build active schedules. So not only is the search space reduced, but also we can build active schedules as well. However, to build active schedules, decisions must be made while the schedule is being generated, which require looking ahead in time. Looking ahead in time is surprisingly computationally expensive, because it requires many programming loops. For example, the GT algorithm looks ahead a certain amount of time from the current period to see which operations will become available for processing on a given machine. A decision must be made as to which operation to process from those that need that machine. This process must happen for each operation in a JSP, and can take a significant amount of time. This could make using a priority list not worth the benefit of the reduced search space property of the GT algorithm.
5.3 The JSP/PSO idea
The research objectives of this study have two-fold. The first was to apply a well-known successful meta-heuristic optimization method, the PSO algorithm, to the JSP. The second stemmed from the first, which was to use it to solve the JSP indirectly with a priority list because of the reduced search space as discussed previously. The easiest way to make each particle a solution to a JSP would be to have each particle have n×m dimensions. Then by using the space transformation procedure discussed earlier, the particle could then be turned into a permutation with repetition schedule representation. This way each particle represents a possible valid schedule. However, even for a small (10 × 5) JSP, a particle would have to have 50 dimensions, and the search space becomes 4.912 × 1043. As shown before, the same problem's search space represented by a priority list is (10!) 5 , or 6.2924 × 1032. So, the second research objective became using the priority list representation instead of permutation with repetition.
Unfortunately, however, because of the way the PSO algorithm works, i.e. information is extracted solely through its position in n dimensional space. So, in order for each particle to represent a complete solution, every operation in a JSP must get its own dimension in a particle. This means that even if a priority list representation is used, there still must be a dimension for every number in the priority list. This does not ultimately reduce the search space. This dilemma is shown graphically in Figure 11. Several creative ways could be developed to make this transformation, but in the end a permutation of length n×m will be required. The figure shows how having a partitioned permutation of length n×m that divides up into a priority list does not reduce the search space to (n!) m , as was the goal. Therefore, some other course must be taken. To accomplish this task, the JSP/PSO encodes only part of a solution into a single particle, and several particles will combined together to make a solution. Since, the goal is to solve the JSP by optimizing a priority list, the priority list will be divided by the number of machines in the JSP, and a single particle will represent one machine's priority list. So for a (10 × 5) JSP (ten jobs and five machines), there will be five particles that combine to make a solution, each one representing a processing priority of length n (see Figure 12 for an illustration). A detailed illustration of the whole concept is shown in Figure 12.
Using this technique, the search space has effectively become n! for each particle, and taken together as a whole the search space is (n!) m . Now, some questions arise at this point as to how the PSO will work in this fashion, because each particle only represents a partial solution to the problem. It is clear there must be several particles in a “swarm,” so that a global best position can be shared with other particles. However, the global best position of the particles representing the operating priority for Machine 1 is not going to be the best position for the particles representing the operating priority for Machine 2. Therefore, in the JSP/PSO there are m number of swarms, one for each machine. This is simply shown in Figure 13.
Each machine in the JSP has its own swarm and thereby it is own global best for the particles to work toward. Which makes sense, because each machines priority list will naturally be different. Notice, that the swarm size is 7 even though there are actually 35 particles. The personal best for each particle and the global best for each swarm are determined by the makespan of the solution to the JSP that they represent a partial solution to, 1/m to be exact. As stated earlier, one particle from each swarm together represents a solution to the JSP problem. Which particles are combined with which particles to form a complete solution is a critical variable in this process. In the JSP/PSO algorithm, one particle in each swarm is “linked” to one other particle in every other swarm and they remain “linked” together through the course of the optimization. The linking is done at initialization and it is done randomly. Of course, there is no actual real link (they do not share information), basically this means that the same particles from every swarm will always come together to form a solution. In other words, “linked” particles share the same “fitness,” so to speak, every iteration. This is shown graphically in Figure 14.
This is an important concept to understand. Essentially, these particles move with no knowledge of the other swarms, but their “fitness” or their best position in space is definitely affected by the position of the other particles “linked” to it in the other swarms.
At first, this may not seem like it should work as an optimization method, and this space division concept may not work well for other meta-heuristic methods, but because the PSO requires that the particles store knowledge of their personal best position and the global best position in space the PSO can be used in this situation. When a better makespan is found by a certain set of linked particles, m number of separate best positions are recorded, one for each of the m different swarms. If this makespan happens to be the best one obtained so far, then each swarm notes that respective position obtained by the particle in their swarm as the global best. Just because those particles have no knowledge of the other swarms does not mean they would not work together indirectly to explore areas that brought them the best fitness in the past. This idea is attempted to be shown graphically in Figure 15. The arrows signify a pull in that direction. It might be easy to understand now why particles should for the most part remain linked to the same particles in other swarms throughout the optimization process. It should be intuitively apparent that “re-linking” particles whose personal best positions were found as a part of another set of linked particles would not be helpful. However, under the right conditions this could be an interesting and possibly beneficial mutation operator.
5.4 Why PSO?
As stated earlier, we believe that PSO is particularly well-suited to be the meta-heuristic method to optimize the JSP in the fashion described in the previous subsection, specifically the division of the search space by the number of machines in a particular JSP. The PSO algorithm makes this possible by the knowledge each particle contains. The ability to simply give the particles a search direction by the parameters of the PSO to either explore new territory or to exploit previously known territory makes the optimization method even more controllable. This makes the particles to work together in an indirect fashion. Also, the fact that the particles are not assigned a specific fitness, but simply contain knowledge of where good positions are in their search space makes this way of solving the JSP realistic. Since particles in other swarms will be drawn to the areas in their space that corresponded with the good positions of the particles in the other swarms. It would be interesting to see how other proven meta-heuristic optimization methods would perform in place of the PSO for this optimization strategy.
Another reason, I believe that the PSO is worth exploring as a possible optimization method in the JSP is because of the unique ability it has in combination with the space transformation technique to search permutation space. The space transformation from continuous space to permutation space has a unique ability to search permutation space. For example, let us say for a (6 × 6) JSP (six jobs and six machines) a particle representing 1/6th of a priority list has the following dimensional and permutation values shown in Figure 16.
Now, for simplicity lets assume that the particle is traveling significantly in only one direction or one dimension, say 3D. If the velocity and position update PSO equations change this dimensional value significantly from 0.6 to 0.15, then a drastic change has taken place in the permutation space, while the particle in the continuous space remains relatively the same. This is shown in Figure 17. The permutation has changed fairly drastically by moving the particle in only one direction. This should give an example of the kind of ability that PSO along with the GVP space transformation rule has to search permutation space. The ability of a particle to move significantly in any dimension can be govern by the values of the user defined coefficients of the PSO equations. Also, by imposing maximum velocity constraints, we can effectively limit the change in any particles position from iteration to iteration.
6 Numerical study
To test the proposed algorithm, two well-known benchmark testing suites were used, the MT suite (Fenton and Walsh, 2005) which consist of three problems, and the LA suite (Lawrence, 1984), which consists of 40 problems. The computational expense of the GT algorithm made itself apparent during the course of the testing procedures, especially when attempting to search total active schedule space. For this reason, the results of the JSP/PSO algorithm presented in this section are from using non-delay schedule building. Recall, that the ability to build either a non-delay schedule, an active schedule, or a parameterized active schedule lies in the 3rd step of the GT algorithm as explained in Section 2.
For comparative purposes the results from a recent publication are shown first in Table V. These results are from Liu et al. (2006). They used a multi-agent system and permutation with repetition to let each agent represent a solution to a JSP. Permutation with repetition was discussed previously in Section 2. These are some of the most current and impressive results in JSP literature today. The optimal solution was found for every one of the 18 problems considered below. The averages in the table are from 100 independent runs. As explained before the permutation with repetition represents solutions in semi-active schedule space. This fact is a drawback of this representation form, because optimal schedules lie in active schedule space. In order for this form to represent solutions in active, or non-delay space a more complicated scheduling algorithm would have to accompany the representation, which would then decrease the speed inherent to that form. The JSP/PSO results are presented in Table VI. Each problem was tested 15 times to make up the averages listed. Every trial was either terminated by obtaining the optimal solution or by reaching the maximum iteration value of 2,000.
6.1 Comparative analysis
The results from the JSP/PSO, presented in Table VI, using non-delay schedule building are very good, but polarized. With the exception of LA15, the optimal solution was either found exactly all 15 times, or found none of the times. One might attribute this to the fact that the solutions to the problems that were never found might not lie in the space of non-delay schedules, or perhaps the size of the problems were too large for the given amount of iterations allowed. This is a disadvantage of searching only non-delay schedule space. However, in every problem solved optimally by the JSP/PSO, with the one exception of LA11, the number of function evaluations was much less than the multi-agent system. This means that for finding optimal non-delay solutions the JSP/PSO has an advantage over the multi-agent system. For example, the average number of function evaluations it took for the JSP/PSO to solve the LA01 problem optimally 15 times is 441.33, where it took (Liu et al., 2006) an average of 1,631 function evaluations. A more drastic difference can be seen in the MT20 problem. The JSP/PSO never solved this problem optimally in any of the three sets, however, in the non-delay set its average makespan value came close to matching the same average makespan value of Liu et al. (2006), but its average function evaluations was only 19,007 compared to 3,106,852 of Liu et al. (2006). This is a common occurrence throughout all testing functions, that is, the fact that Liu et al. (2006) had to perform several million function evaluations to arrive at the optimal solution. However, what is perhaps more significant here is the fact that the space division concept scheme works. The division of the search space by machine was successful in solving JSPs despite the fact that there was no communication between any of the swarms. This idea can be built upon for future work.
7 Conclusions
The proposed JSP/PSO algorithm is capable of solving JSPs. Through the division of the search space by the machines, the proposed algorithm showed considerable promise when searching the space of non-delay schedules. One point worthy of mentioning is the relatively low number of function evaluations needed to find optimal schedules with the use of the proposed design. This space division technique shows that independent swarms or populations working toward a common goal may not have to have knowledge of such a “group effort” if the PSO is used. This is because of the memory characteristic of the PSO.
The possibility of greater success is fully expected in future work by an algorithm that uses the same search space division, but does facilitate information sharing between separate swarms. It stands to reason that if the proposed JSP/PSO algorithm can work to solve small to medium JSPs, then a better algorithm that specifies a way of sharing information between swarms could do much better. It would also be interesting to see how direct representation would work in conjunction with this space division concept. The main disadvantage right now of the JSP/PSO is its use of the GT algorithm. Direct representation would eliminate the need for a scheduling algorithm all together. The concept could then be tested on larger JSPs. More future work could be conducted on using the space division or separate machine swarms concept to manipulate the PSO constants for each swarm independently. For example, perhaps encouraging all swarms to exploit personal found bests, while one swarm is encouraged to explore new space would produce good results. Every machine's swarm would take turn exploring while the rest of the swarms exploit previously good territory. This idea is unique to the “separate swarm search space division concept” implemented by the JSP/PSO. This research has shown that the unique characteristics of both the PSO technique and the JSP fit well with a search space division concept and has laid a foundation for more of the same idea to be explored or built upon.
Equation 1
Gary G. Yen
Brian Ivers
Figure 1Non-semi-active schedule example
Figure 2Semi-active schedule example
Figure 3Left shifting (a)
Figure 4Left shifting (b)
Figure 5Active schedule after left shifting
Figure 6Non-delay schedule
Figure 7Active schedule example
Figure 8Block diagram of PSO/JSP algorithm
Figure 9Space transformation
Figure 10Permutation with repetition schedule
Figure 11Priority list to a particle (a)
Figure 12JSP/PSO block diagram
Figure 13JSP/PSO swarm for an n×5 JSP
Figure 14JSP/PSO linking
Figure 15JSP/PSO personal and global best position
Figure 16Six dimensional particle in continuous and permutation space (a)
Figure 17Six dimensional particle in continuous and permutation space (b)
Table IExample of scheduling problem
Table IISimple JSP example
Table IIIPriority list representation
Table IVSimple job shop scheduling problem
Table VComparative results
Table VINon-delay JSP/PSO results
References
Bierwirth, C.A. (1995), "Generalized permutation approach to job shop scheduling with genetic algorithms", OR Spektrum, Vol. 17 pp.87-92.
Chang, Y.L., Sueyoshi, T., Sullivan, R.S. (1996), "Ranking dispatching rules by data envelopment analysis in a job-shop environment", IIE Transactions, Vol. 28 No.8, pp.631-42.
Davis, L. (1985), "Job shop scheduling with genetic algorithms", Proceedings of the 1st International Conference on Genetic Algorithms, Pittsburgh, PA, pp.136-40.
Dimopoulos, C., Zalzala, A. (2000), "Recent developments in evolutionary computation for manufacturing optimization: problems, solutions, and comparisons", IEEE Trans. Evolutionary Computation, Vol. 4 pp.93-113.
Eberhard, R.C., Kennedy, J. (1995), "A new optimizer using particle swarm theory", Proceedings of the International Symposium on Micro Machine and Human Science, Nagoya, Japan, pp.39-43.
Fenton, P., Walsh, P. (2005), "Improving the performance of the repeating permutation representation using morphogenic computation and generalized modified order crossover", The 2005 IEEE Congress on Evolutionary Computation, Vol. 2 pp.1372-9.
Giffler, B., Thompson, G.L. (1960), "Algorithms for solving production scheduling problems", Operations Research, Vol. 8 No.4, pp.487-503.
Jackson, J.R. (1955), "Scheduling a production line to minimize maximum tardiness", University of California, Los Angeles, CA, Research Report 43, Management Science Research Projects, .
Jackson, J.R. (1957), "Simulation research on job-shop production", Naval Research Logistics Quarterly, Vol. 4 pp.287-95.
Jain, A.S., Meeran, S. (1999), "A state-of-the-art review of job-shop scheduling techniques", European Journal of Operations Research, Vol. 113 pp.390-434.
Lawrence, S. (1984), "Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques", Carnegie Mellon University, Pittsburgh, PA, Technical Report, .
Lian, Z., Gu, X., Jiao, B. (2005), "A similar particle swarm optimization algorithm for permutation flowshop scheduling to minimize makespan", Applied Mathematics and Computation, Vol. 12 pp.124-32.
Liu, J., Zhong, W., Jiao, L. (2006), "A multiagent evolutionary algorithm for constraint satisfaction problems", IEEE Trans. Systems, Man, and Cybernetics – Part B: Cybernetics, Vol. 36 pp.54-73.
Muth, J.F., Thompson, G.L. (1963), Industrial Scheduling, Prentice-Hall, Englewood Cliffs, NJ, .
Pang, W., Wang, K., Zhou, C., Dong, L., Liu, M., Zhang, H., Wang, J. (2004), "Modified particle swarm optimization based on space transformation for solving traveling salesman problem", Proceedings of the International Conference on Machine Learning and Cybernetics, Shanghai, China, pp.26-9.
Pirlot, M. (1996), "General local search methods", European Journal of Operational Research, Vol. 92 pp.493-511.
Rowe, A.J., Jackson, J.R. (1956), "Research problems in production routing and scheduling", Journal of Industrial Engineering, Vol. 7 pp.116-21.
Smith, W.E. (1956), "Various optimizers for single stage production", Naval Research Logistics Quarterly, Vol. 3 pp.59-66.
Song, M., Gu, G. (2004), "Research on particle swarm optimization: a review", Proceedings of the International Conference on Machine Learning and Cybernetics, Shanghai, China, pp.30-3.
Tasgetiren, M.F., Liang, Y.C., Sevkli, M., Gencyilmaz, G. (2004a), "Particle swarm optimization algorithm for makespan and maximum lateness minimization in permutation flowshop problem", Proceedings of the International Symposium on Intelligent Manufacturing Systems, Sakarya, Turkey, pp.431-41.
Tasgetiren, M.F., Sevkli, M., Liang, Y.C., Gencyilmaz, G. (2004b), "Particle swarm optimization algorithm for single-machine total weighted tardiness problem", Proceedings of Congress on Evolutionary Computation, Portland, OR, pp.19-23.
Wang, K., Huang, L., Zhou, C., Pang, W. (2003), "Particle swarm optimization for traveling salesman problem", Proceedings of the International Conference on Machine Learning and Cybernetics, Xi'an, China, pp.2-5.
Xia, W., Wu, Z. (2005), "An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems", Computers & Industrial Engineering, Vol. 48 pp.409-25.
Xia, W., Wu, Z., Zhang, W., Yang, G. (2004), "A new hybrid optimization algorithm for the job shop scheduling problem", Proceedings of the American Control Conference, Boston, MA, pp.5552-7.
About the authors
Gary G. Yen received the PhD degree in Electrical and Computer Engineering from the University of Notre Dame, Notre Dame, IN in 1992. He is currently a Professor in the School of Electrical and Computer Engineering, Oklahoma State University (OSU), Stillwater, OK, USA. Before he joined OSU in 1997, he was with the Structure Control Division, US Air Force Research Laboratory in Albuquerque, NM, USA. His research is supported in part by the DoD, DoE, EPA, NASA, NSF, and Process Industry. His research interest includes intelligent control, computational intelligence, conditional health monitoring, signal processing and their industrial/defense applications. He was an Associate Editor of the IEEE Transactions on Neural Networks, IEEE Control Systems Magazine, IEEE Transactions on Control Systems Technology, IEEE Transactions on Systems, Man and Cybernetics and IFAC Journal on Automatica. He is currently serving as an Associate Editor for the IEEE Transactions on Evolutionary Computation and Mechatronics. He is currently serving as the Founding Editor-in-chief of the IEEE Computational Intelligence Magazine. He served as the General Chair for the 2003 IEEE International Symposium on Intelligent Control held in Houston, TX and 2006 IEEE World Congress on Computational Intelligence held in Vancouver, Canada. He served as Vice President for the Technical Activities, IEEE Computational Intelligence Society and has been elected to serve as President of the CIS in 2010. Gary G. Yen is the corresponding author and can be contacted at: gyen@okstate.edu; and his personal web site: www.okstate.edu/elec-engr/faculty/yen
Brian Ivers received a BS in Computer Engineering from OSU in 1999, and a MS in Electrical Engineering from OSU in 2001. He is currently working as a Software Engineer for Frontier Electronic Systems Corp. in Stillwater, OK, USA. Recently, he has completed the hardware and software design for the Targeting Electronic Displays and Controls Display for the AH-64 Apache Aircrew Training System. He is the process owner for FES' Software Development Procedures, and has updated these procedures to be compliant with the Software Engineering Institute's Level 3 Capability Maturity Model.
