A Robust Heuristics for the Online Job Shop Scheduling Problem
The job shop scheduling problem (JSSP) is a popular NP-hard problem in combinatorial optimization, due to its theoretical appeal and its importance in applications. In practical applications, the online version is much closer to the needs of smart manufacturing in Industry 4.0 and 5.0. Here, the onl...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2024-12-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/17/12/568 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1850036473223446528 |
|---|---|
| author | Hugo Zupan Niko Herakovič Janez Žerovnik |
| author_facet | Hugo Zupan Niko Herakovič Janez Žerovnik |
| author_sort | Hugo Zupan |
| collection | DOAJ |
| description | The job shop scheduling problem (JSSP) is a popular NP-hard problem in combinatorial optimization, due to its theoretical appeal and its importance in applications. In practical applications, the online version is much closer to the needs of smart manufacturing in Industry 4.0 and 5.0. Here, the online version of the job shop scheduling problem is solved by a heuristics that governs local queues at the machines. This enables a distributed implementation, i.e., a digital twin can be maintained by local processors which can result in high speed real time operation. The heuristics at the level of probabilistic rules for running the local queues is experimentally shown to provide the solutions of quality that is within acceptable approximation ratios to the best known solutions obtained by the best online algorithms. The probabilistic rule defines a model which is not unlike the spin glass models that are closely related to quantum computing. Major advances of the approach are the inherent parallelism and its robustness, promising natural and likely successful application to other variations of JSSP. Experimental results show that the heuristics, although designed for solving the online version, can provide near-optimal and often even optimal solutions for many benchmark instances of the offline version of JSSP. It is also demonstrated that the best solutions of the new heuristics clearly improve over the results obtained by heuristics based on standard dispatching rules. Of course, there is a trade-off between better computational time and the quality of the results in terms of makespan criteria. |
| format | Article |
| id | doaj-art-7e7fcd9359544404a73a2549c7a069f4 |
| institution | DOAJ |
| issn | 1999-4893 |
| language | English |
| publishDate | 2024-12-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Algorithms |
| spelling | doaj-art-7e7fcd9359544404a73a2549c7a069f42025-08-20T02:57:08ZengMDPI AGAlgorithms1999-48932024-12-01171256810.3390/a17120568A Robust Heuristics for the Online Job Shop Scheduling ProblemHugo Zupan0Niko Herakovič1Janez Žerovnik2Faculty of Mechanical Engineering, Aškerčeva cesta 6, 1000 Ljubljana, SloveniaFaculty of Mechanical Engineering, Aškerčeva cesta 6, 1000 Ljubljana, SloveniaFaculty of Mechanical Engineering, Aškerčeva cesta 6, 1000 Ljubljana, SloveniaThe job shop scheduling problem (JSSP) is a popular NP-hard problem in combinatorial optimization, due to its theoretical appeal and its importance in applications. In practical applications, the online version is much closer to the needs of smart manufacturing in Industry 4.0 and 5.0. Here, the online version of the job shop scheduling problem is solved by a heuristics that governs local queues at the machines. This enables a distributed implementation, i.e., a digital twin can be maintained by local processors which can result in high speed real time operation. The heuristics at the level of probabilistic rules for running the local queues is experimentally shown to provide the solutions of quality that is within acceptable approximation ratios to the best known solutions obtained by the best online algorithms. The probabilistic rule defines a model which is not unlike the spin glass models that are closely related to quantum computing. Major advances of the approach are the inherent parallelism and its robustness, promising natural and likely successful application to other variations of JSSP. Experimental results show that the heuristics, although designed for solving the online version, can provide near-optimal and often even optimal solutions for many benchmark instances of the offline version of JSSP. It is also demonstrated that the best solutions of the new heuristics clearly improve over the results obtained by heuristics based on standard dispatching rules. Of course, there is a trade-off between better computational time and the quality of the results in terms of makespan criteria.https://www.mdpi.com/1999-4893/17/12/568job shop scheduling problemonline algorithmheuristicssimulationdigital twinsmart manufacturing |
| spellingShingle | Hugo Zupan Niko Herakovič Janez Žerovnik A Robust Heuristics for the Online Job Shop Scheduling Problem Algorithms job shop scheduling problem online algorithm heuristics simulation digital twin smart manufacturing |
| title | A Robust Heuristics for the Online Job Shop Scheduling Problem |
| title_full | A Robust Heuristics for the Online Job Shop Scheduling Problem |
| title_fullStr | A Robust Heuristics for the Online Job Shop Scheduling Problem |
| title_full_unstemmed | A Robust Heuristics for the Online Job Shop Scheduling Problem |
| title_short | A Robust Heuristics for the Online Job Shop Scheduling Problem |
| title_sort | robust heuristics for the online job shop scheduling problem |
| topic | job shop scheduling problem online algorithm heuristics simulation digital twin smart manufacturing |
| url | https://www.mdpi.com/1999-4893/17/12/568 |
| work_keys_str_mv | AT hugozupan arobustheuristicsfortheonlinejobshopschedulingproblem AT nikoherakovic arobustheuristicsfortheonlinejobshopschedulingproblem AT janezzerovnik arobustheuristicsfortheonlinejobshopschedulingproblem AT hugozupan robustheuristicsfortheonlinejobshopschedulingproblem AT nikoherakovic robustheuristicsfortheonlinejobshopschedulingproblem AT janezzerovnik robustheuristicsfortheonlinejobshopschedulingproblem |