An Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with Random Processing Times
Due to the influence of unpredictable random events, the processing time of each operation should be treated as random variables if we aim at a robust production schedule. However, compared with the extensive research on the deterministic model, the stochastic job shop scheduling problem (SJSSP) has...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2011-09-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | http://www.mdpi.com/1099-4300/13/9/1708/ |
| _version_ | 1828145919550291968 |
|---|---|
| author | Rui Zhang Cheng Wu |
| author_facet | Rui Zhang Cheng Wu |
| author_sort | Rui Zhang |
| collection | DOAJ |
| description | Due to the influence of unpredictable random events, the processing time of each operation should be treated as random variables if we aim at a robust production schedule. However, compared with the extensive research on the deterministic model, the stochastic job shop scheduling problem (SJSSP) has not received sufficient attention. In this paper, we propose an artificial bee colony (ABC) algorithm for SJSSP with the objective of minimizing the maximum lateness (which is an index of service quality). First, we propose a performance estimate for preliminary screening of the candidate solutions. Then, the K-armed bandit model is utilized for reducing the computational burden in the exact evaluation (through Monte Carlo simulation) process. Finally, the computational results on different-scale test problems validate the effectiveness and efficiency of the proposed approach. |
| first_indexed | 2024-04-11T20:39:29Z |
| format | Article |
| id | doaj.art-1344d1bbc95f41ff86421d09731c747d |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-04-11T20:39:29Z |
| publishDate | 2011-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-1344d1bbc95f41ff86421d09731c747d2022-12-22T04:04:14ZengMDPI AGEntropy1099-43002011-09-011391708172910.3390/e13091708An Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with Random Processing TimesRui ZhangCheng WuDue to the influence of unpredictable random events, the processing time of each operation should be treated as random variables if we aim at a robust production schedule. However, compared with the extensive research on the deterministic model, the stochastic job shop scheduling problem (SJSSP) has not received sufficient attention. In this paper, we propose an artificial bee colony (ABC) algorithm for SJSSP with the objective of minimizing the maximum lateness (which is an index of service quality). First, we propose a performance estimate for preliminary screening of the candidate solutions. Then, the K-armed bandit model is utilized for reducing the computational burden in the exact evaluation (through Monte Carlo simulation) process. Finally, the computational results on different-scale test problems validate the effectiveness and efficiency of the proposed approach.http://www.mdpi.com/1099-4300/13/9/1708/shop schedulingartificial bee colony algorithmmaximum latenesssimulation |
| spellingShingle | Rui Zhang Cheng Wu An Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with Random Processing Times Entropy shop scheduling artificial bee colony algorithm maximum lateness simulation |
| title | An Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with Random Processing Times |
| title_full | An Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with Random Processing Times |
| title_fullStr | An Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with Random Processing Times |
| title_full_unstemmed | An Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with Random Processing Times |
| title_short | An Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with Random Processing Times |
| title_sort | artificial bee colony algorithm for the job shop scheduling problem with random processing times |
| topic | shop scheduling artificial bee colony algorithm maximum lateness simulation |
| url | http://www.mdpi.com/1099-4300/13/9/1708/ |
| work_keys_str_mv | AT ruizhang anartificialbeecolonyalgorithmforthejobshopschedulingproblemwithrandomprocessingtimes AT chengwu anartificialbeecolonyalgorithmforthejobshopschedulingproblemwithrandomprocessingtimes AT ruizhang artificialbeecolonyalgorithmforthejobshopschedulingproblemwithrandomprocessingtimes AT chengwu artificialbeecolonyalgorithmforthejobshopschedulingproblemwithrandomprocessingtimes |