Προγραμματισμός Εργασιών σε Εργαστήριο (Job Shop Scheduling)

Ο προγραμματισμός εργασιών σε εργαστήριο (job shop scheduling) είναι το πρόβλημα της ανάθεσης ενός συνόλου εργασιών (tasks) σε ένα σύνολο μηχανών (resources) με την πάροδο του χρόνου, υπό την προϋπόθεση περιορισμών προτεραιότητας και χωρητικότητας, με στόχο τη βελτιστοποίηση μετρικών απόδοσης όπως ο χρόνος ολοκλήρωσης (makespan), η καθυστέρηση (lateness) ή το κόστος. Το πρόβλημα του job shop είναι ένα κλασικό πρόβλημα συνδυαστικής βελτιστοποίησης στην έρευνα επιχειρησιακών λειτουργιών, το οποίο αντιμετωπίζεται μέσω ευριστικών μεθόδων (κανόνες δρομολόγησης απληστίας, προσομοιωμένη ανόπτηση, γενετικοί αλγόριθμοι) και ακριβών αλγορίθμων (branch-and-bound, προγραμματισμός περιορισμών). Είναι θεμελιώδες για την παραγωγή, τη διαχείριση έργων και τον υπολογιστικό προγραμματισμό.