20.500.12556/RUL-165876 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 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. job shop scheduling problems online algorithms heuristics simulations digital twins smart manufacturing true false true Angleški jezik Angleški jezik Članek v reviji 2024-12-12 13:32:49 2024-12-12 13:32:53 2024-12-13 03:57:49 0000-00-00 00:00:00 2024 0 0 20 str. iss. 12, [art. no.] 568 Vol. 17 2024 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 658.5 1999-4893 10.3390/a17120568 218819075 Zupan_..._A_Robust_Heuristics_for_the_Online_Job_Shop_Scheduling_Problem.pdf Zupan_..._A_Robust_Heuristics_for_the_Online_Job_Shop_Scheduling_Problem.pdf 1 9FB7EC375C646AB4F855EB4BA4D1CD80 403fb5ef92c990a954006c95cd54b6df6a31e8f854660833dcee796b9becde0e e595bb75-b884-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=197143 https://www.mdpi.com/1999-4893/17/12/568 1 b516f971-b884-11ef-b232-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=197142 Fakulteta za strojništvo 0 0 0