A robust heuristics for the online job shop scheduling problem

Zupan, Hugo (author), Herakovič, Niko (author), Žerovnik, Janez (author)

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.

• Language: English
• Keywords: job shop scheduling problems, online algorithms, heuristics, simulations, digital twins, smart manufacturing
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FS - Faculty of Mechanical Engineering
• Publication status: Published
• Publication version: Version of Record
• Year: 2024
• Number of pages: 20 str.
• Numbering: Vol. 17, iss. 12, [art. no.] 568
• PID: 20.500.12556/RUL-165876
• UDC: 658.5
• ISSN on article: 1999-4893
• DOI: 10.3390/a17120568
• COBISS.SI-ID: 218819075
• Publication date in RUL: 12.12.2024

Record is a part of a journal

• Title: Algorithms
• Shortened title: Algorithms
• Publisher: MDPI
• ISSN: 1999-4893
• COBISS.SI-ID: 517501977

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.