| Author | Pisut Pongchairerks |
| Call Number | AIT Diss. no.ISE-08-01 |
| Subject(s) | Production scheduling
|
| Note | A dissertation submitted in partial fulfillment of the requirements for the degree of Doctor of Engineering, School of Engineering and Technology |
| Publisher | Asian Institute of Technology |
| Series Statement | Dissertation ; no. ISE-08-01 |
| Abstract | Scheduling is a decision making process to allocate limited resources over time to perform tasks. It usually uses manufacturing terminology, where jobs represent tasks and machines represent resources. The domain of scheduling is not only limited to manufacturing but also includes logistic and transportation, procurement and production, information processing and communications, service business, etc. A proper schedule enables an organization to achieve its goal and gain the optimum benefit. Unfortunately, many important scheduling problems are very difficult and consume extremely long computation time to find optimal schedules through existing exact algorithms. To overcome the difficulties mentioned, this thesis develops algorithms which can generate efficient schedules within an acceptable computation time. This research focuses on very difficult scheduling problems such as job-shop scheduling problem, job-shop scheduling problem with multi-purpose machine, and open-shop scheduling problem. In order to achieve the objective mentioned above, this thesis applies PSG (i.e. a stochastic search algorithm based on the simulated swarm behavior) as the framework of the proposed scheduling algorithms. The reason is that the potential of PSG had been demonstrated in many recent successful researches as a key approach to solve several engineering problems. A variant of the standard PSG with multiple social learning structures is proposed. In addition, scheduling algorithms are proposed based on the proposed PSO variant. The performance of the proposed algorithm is evaluated for job¬shop scheduling problem on a set of benchmark instances. Based on the evaluation results, the deviation between the optimal solution value and the best found solution value is 1.25% on average. The performance of the algorithm for open-shop scheduling problem is evaluated on three sets of benchmark instances. Based on the results, the average deviations between the optimal solution value and the best found solution value are ranging from 0.21 % to 0.60%. To make the proposed method easier to use, an automatic parameter tuner is added to the proposed scheduling problems. This parameter tuner is also based on PSO. The proposed job-shop scheduling algorithm combined with the parameter tuner is evaluated on the same set of benchmark instances. The evaluation results show the average deviation between the optimal solution value and the best found solution value is only 0.35%. Similarly, the proposed open-shop scheduling algorithm combined with the parameter tuner also outperforms the open-shop scheduling algorithm in terms of solution quality. Its performance is tested on the same sets of instances. Based on the test results, the average deviations are ranging from 0.00% to 0.18% |
| Year | 2008 |
| Corresponding Series Added Entry | Asian Institute of Technology. Dissertation ; no. ISE-08-01 |
| 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) | Huynh Trung Luong ;Weerakorn Ongsakul ; |
| Scholarship Donor(s) | Royal Thai Government Fellowship; |
| Degree | Thesis (Ph.D.) - Asian Institute of Technology, 2008 |