A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Makespan
The Job-shop scheduling problem (JSSP) is a branch of production scheduling, which is among the hardest combinatorial optimization problems. Many different approaches have been applied to optimize JSSP, but for some JSSP even with moderate size cannot be solved to guarantee optimality. The original...
Saved in:
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2010-01-01
|
| Series: | Discrete Dynamics in Nature and Society |
| Online Access: | http://dx.doi.org/10.1155/2010/838596 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832566826235592704 |
|---|---|
| author | Zhigang Lian |
| author_facet | Zhigang Lian |
| author_sort | Zhigang Lian |
| collection | DOAJ |
| description | The Job-shop scheduling problem (JSSP) is a branch of production scheduling, which is among the hardest combinatorial optimization problems. Many different approaches have been applied to optimize JSSP, but for some JSSP even with moderate size cannot be solved to guarantee optimality. The original particle swarm optimization algorithm (OPSOA), generally, is used to solve continuous problems, and rarely to optimize discrete problems such as JSSP. In OPSOA, through research I find that it has a tendency to get stuck in a near optimal solution especially for middle and large size problems. The local and global search combine particle swarm optimization algorithm (LGSCPSOA) is used to solve JSSP, where particle-updating mechanism benefits from the searching experience of one particle itself, the best of all particles in the swarm, and the best of particles in neighborhood population. The new coding method is used in LGSCPSOA to optimize JSSP, and it gets all sequences are feasible solutions. Three representative instances are made computational experiment, and simulation shows that the LGSCPSOA is efficacious for JSSP to minimize makespan. |
| format | Article |
| id | doaj-art-7332bc397cb64cc4b0dde75d7a4c770b |
| institution | Kabale University |
| issn | 1026-0226 1607-887X |
| language | English |
| publishDate | 2010-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Discrete Dynamics in Nature and Society |
| spelling | doaj-art-7332bc397cb64cc4b0dde75d7a4c770b2025-02-03T01:03:11ZengWileyDiscrete Dynamics in Nature and Society1026-02261607-887X2010-01-01201010.1155/2010/838596838596A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize MakespanZhigang Lian0School of Electronic and Information Engineering, Shanghai DianJi University, Shanghai 200240, ChinaThe Job-shop scheduling problem (JSSP) is a branch of production scheduling, which is among the hardest combinatorial optimization problems. Many different approaches have been applied to optimize JSSP, but for some JSSP even with moderate size cannot be solved to guarantee optimality. The original particle swarm optimization algorithm (OPSOA), generally, is used to solve continuous problems, and rarely to optimize discrete problems such as JSSP. In OPSOA, through research I find that it has a tendency to get stuck in a near optimal solution especially for middle and large size problems. The local and global search combine particle swarm optimization algorithm (LGSCPSOA) is used to solve JSSP, where particle-updating mechanism benefits from the searching experience of one particle itself, the best of all particles in the swarm, and the best of particles in neighborhood population. The new coding method is used in LGSCPSOA to optimize JSSP, and it gets all sequences are feasible solutions. Three representative instances are made computational experiment, and simulation shows that the LGSCPSOA is efficacious for JSSP to minimize makespan.http://dx.doi.org/10.1155/2010/838596 |
| spellingShingle | Zhigang Lian A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Makespan Discrete Dynamics in Nature and Society |
| title | A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Makespan |
| title_full | A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Makespan |
| title_fullStr | A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Makespan |
| title_full_unstemmed | A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Makespan |
| title_short | A Local and Global Search Combine Particle Swarm Optimization Algorithm for Job-Shop Scheduling to Minimize Makespan |
| title_sort | local and global search combine particle swarm optimization algorithm for job shop scheduling to minimize makespan |
| url | http://dx.doi.org/10.1155/2010/838596 |
| work_keys_str_mv | AT zhiganglian alocalandglobalsearchcombineparticleswarmoptimizationalgorithmforjobshopschedulingtominimizemakespan AT zhiganglian localandglobalsearchcombineparticleswarmoptimizationalgorithmforjobshopschedulingtominimizemakespan |