אלגוריתם יעיל לשיבוץ עבודה-תחנה, המבוסס על אופטימיזציית נחיל חלקיקים
Lin et al., 2010
מבוא
נושא המאמר הוא בעיית שיבוץ עבודה-תחנה (Job-shop scheduling), ופתרונה באמצעות אלגוריתם המבוסס על נחיל חלקיקים. הבעיה המחקרית היא שעד הצעת האלגוריתם שמציעים החוקרים, לא הוצע אלגוריתם יעיל לפתרון בעיית שיבוץ עבודה-תחנה (בקיצור: JSSP), למרות שבעיה זו מעסיקה חוקרים רבים גם בתחום מדעי המחשב וגם בתחום ניהול התפעול.
החידוש במאמר הוא שהמאמר מציע, לראשונה, פתרון יעיל ל-JSSP, המבוסס אלגוריתם אינטליגנציית נחיל היברידית שמורכב משילוב של אופטימיזציית נחיל חלקיקים (particle swarm), טכניקת הדמיית ליבון (simulated annealing), וסכמת שיפור לפרטים מסוגים מרובים (multi-type individual enhancement scheme). אלגוריתם חדשני זה צפוי להביא לשיפור ביעילות של פתרון בעיות מסוג שיבוץ תחנה-עבודה (Job-shop scheduling).
הסבר על הבעיה ומאפייניה
בעיית שיבוץ עבודה-תחנה (JSSP) היא בעיית אופטימיזציה קומבינטורית ידועה ונחשבת לNP-קשה. בבעיית שיבוץ עבודה-תחנה, כל אחת מ-n עבודות צריכה להיות מעובדת ב-m מכונות ברצף נתון. רצף המכונות יכול להיות שונה עבור כל עבודה, ולא ניתן לשנות אותו במהלך העיבוד. כמו כן, עיבוד של כל עבודה בכל מכונה עשוי לקחת זמן שונה.
כל עיבוד של עבודה מסויימת על ידי מכונה מסויימת נקרא אופרציה. בכל רגע נתון, כל מכונה יכולה לעבד רק עבודה אחת (לבצע אופרציה אחת), ועבודה יכולה להיות מעובדת על ידי מכונה אחת בכל רגע נתון. המטרה של שיבוץ עבודה-תחנה היא למצוא את השיבוץ שבו סך כל זמן העיבוד (הנקרא makespan) יהיה מינימלי. רמת המורכבות של הבעיה עולה, כמובן, ככל שיש יותר עבודות וככל שיש יותר מכונות (כאשר n ו-m גדולות יותר). לבעיה יישומים רבים בתעשייה (כגון – תכנון ייצור) וכן במחשבים (כגון - עיבוד נתונים)....
לקריאת הסיכום המלא הורד/י את הסיכום באמצעות הטופס לעיל^
