בחינת השפעת אופק תכנון מוגבל על איכות התזמון

המאמר עוסק בפרויקט תיאורטי מחקרי בתחום של תזמון פעולות (למשל פעולות ייצור).

מטרת הפרויקט היא לבחון את השפעת בחירת אופק התכנון של מכונה (או שרת אחר) לפי מדדים המבוססים על זמני השהיה ועל איחורים, באמצעות הרצת סימולציות וניתוח סטטיסטי של התוצאות.

הסימולציה בוצעה באמצעות כתיבת תוכנת מחשב מבוססת גיליון אקסל, המדמה שיבוץ משימות על שרת בודד.

השלב הראשון:

ראשית נבחנו שלוש חלופות. כל חלופה מורכבת משלושה אופקי תכנון בגדלים שונים ושיבוץ המשימות בכל חלופה נעשה בעזרת חוקי סדרור בסיסים כגון:SPT,WSPT EDD .

תוכנת המחשב התבססה על מאגר נתונים המתחדש באופן תדיר אשר סיפק נתונים חדשים לכל הפעלה. בחנו את ההשפעה על התזמון הכולל בעזרת ביצוע מספר רב של תזמונים (הפעלות רבות של התוכנה) והשוואה של תוצאות השיבוץ בין אופקי התכנון של החלופה באמצעות שני ממדים עיקריים:

1. איחורים: לפי מדדי ממוצע סכום האיחורים ומספר משימות מאחרות.
2. זמני שהיה: לפי מדד ממוצע זמני שהיה של המשימות במערכת.

הראינו שבאמצעות השימוש באופקי תכנון בגדלים שונים מתקבל שיפור בשיבוץ המשימות: הראינו כי השיפור בזמני השהיה הוא לינארי ביחס להארכת אופק התכנון ואילו ההשפעה על האיחורים יורדת מתמתנת עם הארכת אופק התכנון.

השלב השני:

בשלב השני של הפרויקט בחנו את האפשרות לשימוש באותם אופקי תכנון תוך מתן מענה לשיפור פונקציית מטרה דו-ממדית: ממוצע איחורים וממוצע זמני שהיה.

על מנת ליצור פתרונות המספקים שיפור מדדים משולב נעשה שימוש באלגוריתם גנטי.

השימוש באלגוריתם הגנטי נעשה ע"י יצירת מספר רב של פתרונות אקראיים לשיבוץ משימות, דירוג פתרונות "האב" הטובים ביותר ובעזרתם, יצירת דורות חדשים של פתרונות בטכניקות שונות. במקרה זה מתקבלת חזית יעילה של פתרונות, אשר משתפרת באופן מתמתן עם הגדלת אופקי התכנון.