| Author | Apinanthana Udomsakdigool |
| Call Number | AIT Diss. no.ISE-06-04 |
| Subject(s) | Production scheduling--Algorithms
|
| Note | A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Engineering in Industrial Engineering and Management, School of Engineering and Technology |
| Publisher | Asian Institute of Technology |
| Series Statement | Dissertation ; no. ISE-06-04 |
| Abstract | The job-shop scheduling problem (JSP) is concerned with allocating limited resources to tasks to optimize certain objective functions. The JSP is one of the strongly NP-hard combinatorial optimization problems and is difficult to solve optimally. For pragmatic purpose, several approximation algorithms which can find good solutions in an acceptable time have been developed. This dissertation proposes methods based on Ant Colony Optimization (ACO) technique to dealing with the JSP. The dissertation is divided into two parts as follows. In the first part, a new ACO algorithm called MT Ant for solving the JSP with the objective of minimizing the makespan is developed. Some new features are included in the algorithm to provide better solutions. These features include two-way scheduling and multiple colony ant algorithm approach. The two-way scheduling allows ant to construct the solution in both forward and backward directions. In addition, the multiple colony strategy allows ants to search in different search space and allows colony to benefit from the lesson learned by the other colonies. The performance of the algorithm is tested over 38 well known benchmark problems, 21 problems yield optimal solution and for other problems the deviation from optimal are less than 4%. The performance of the proposed algorithm is superior when compared with previously published research. In the second part the Genetic Algorithm (GA) is used to find good parameter values for the ACO algorithm. The parameters of the ant colony are included in the chromosome. Each individual chromosome represents a parameter setting for the ACO algorithm. Colonies are in competition to make it to the next generation. The fitness of each individual colony is evaluated by running the ant algorithm. This algorithm is a two¬level Ant-GA with the first level using GA and the second level is the ACO algorithm. The performance of the two-level approach is tested on fifteen large size problems and the results show that the two-level approach can find the parameter values which improved on the best solution compared with using the previous parameter set. This proposed method suggests a better way to determine the parameter values for ACO algorithm |
| Year | 2006 |
| Corresponding Series Added Entry | Asian Institute of Technology. Dissertation ; no. ISE-06-04 |
| Type | Dissertation |
| School | School of Engineering and Technology (SET) |
| Department | Department of Industrial Systems Engineering (DISE) |
| Academic Program/FoS | Industrial Systems Engineering (ISE) |
| Chairperson(s) | Voratas Kachitvichyanukul; |
| Examination Committee(s) | Tang, John C.S.;Huynh Trung Luong;Gen, Mitsuo; |
| Scholarship Donor(s) | RTG Fellowship The National Energy Policy Office (NEPO), Ministry of Energy, Thailand King Mongkut's Institute of Technology North Bangkok, Thailand; |
| Degree | Thesis (Ph.D.) - Asian Institute of Technology, 2006 |