נושא הפרוייקט

מספר פרוייקט מחלקה שמות סטודנטים אימייל שמות מנחים

בחינת יעילות של אלגוריתמי תזמון על שתי מכונות במערך זרימה עם דחייה

EFFICIENCY ANALYSIS OF ALGORITHMS FOR SOLVING A TWO MACHINS FLOW-SHOP PROBLEM WITH REJECTION

תקציר בעיברית

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

מטרת הפרויקט הינה לבחון דרכים לקבלת החלטות כלכלית אשר תוביל לאיזון מיטבי בין עלויות דחיית הפעילויות לבין איכות השירות שתינתן עבור הלקוחות שאת הפעילויות שלהם יש לבצע. המחקר בוצע על בעיית תזמון במערך לפי זרימה (Flow Shop) המכיל שתי מכונות כאשר מדד התזמון הינו זמן סיום הביצוע של כלל הפעילויות (Makespan) וניתן לבצע דחייה של כל אחת מהפעילות בעלות מסוימת. כלומר, הקלט לבעיה שנחקרה מכיל את מספר הג'ובים שיש לבצע ((n. בעזרת O_ij נסמן את הפעילות של גו'ב J_j על מכונה M_i. עבור כל פעילותO_ij   נתון הן משך ביצוע (p_ij) והן עלות הדחייה (e_ij(. מטרתנו הינה למצוא פתרון שממזער את הסכום של זמן הסיום המקסימאלי וסך עלויות הדחייה. פתרון לבעיה מוגדר משתי רמות החלטה שאינן ניתנות להפרדה: (i) חלוקה של כלל הפעילויות לשתי תתי קבוצות:O_A  - קבוצת הפעילויות שנבצע ו  O_R – קבוצת הפעילויות שנדחה. (ii) תזמון קבוצת הפעילויות שקיבלנו (השייכות ל-O_A) על שתי המכונות.

מטרות המחקר הינן (i) למידת האלגוריתמים שפותחו על ידי(2022)    Shabtay and Gerstelלפתרון הבעיה אשר נחשבת לבעיית NP השלמה (ii) להציע אלגוריתמים נוספים לפתרון הבעיה (iii) תכנות כלל האלגוריתמים ו (iv) בחינת הביצועים של  כלל האלגוריתמים בשני מישורים: זמן ריצת האלגוריתמים ואיכות ערך הפתרון. בחנו ארבעה אלגוריתמים (אחד מהם פותח במהלך הפרויקט ושלושה נלקחו מהספרות): האלגוריתם הראשון הינו אלגוריתם נאיבי, האלגוריתם השני הינו אלגוריתם חמדני (שני האלגוריתמים מהווים 2 קירוב), אלגוריתם שלישי מבוסס על פתרון הניסוח הלינארי של הבעיה בעזרת תוכנה, ואלגוריתם רביעי הינו גנטי. כלל האלגוריתם תוכנתו בסביבת  PyCharm Pythonולאחר מכן בצענו מחקר ניסויי לבחינת יעילותם.  

התוצאות שהתקבלו מראות שזמני הריצה של האלגוריתם הנאיבי והאלגוריתם החמדני הינם זניחים לכל גודל קלט של הבעיה. לעומת זאת, זמני הריצה של התכנות לינארי והאלגוריתם הגנטי הוגבלו ל-5 דקות. מסיבה זו ביצענו שתי השוואות: השוואה ראשונה התבצעה בין האלגוריתם הנאיבי והאלגוריתם החמדני בעוד שההשוואה השנייה התבצעה בין התכנות לינארי והאלגוריתם הגנטי. כל השוואה חולקה לארבע תתי השוואות, כאשר כל אחת עבור גודל קלט שונה (20, 50, 100 ו-200) ההשוואות בוצעו על ידי מבחן t מזווג ברמת מובהקות של 5%. בהשוואה בין האלגוריתם הנאיבי לאלגוריתם החמדני ביצענו מבחן חד-צדדי, מתוצאות הניסוי אפשר לקבוע כי האלגוריתם החמדני מניב פתרון איכותי יותר. בהשוואה בין התכנות לינארי לבין האלגוריתם הגנטי ביצענו מבחן דו-צדדי, מתוצאות הניסוי היה ניתן לראות כי בגודלי קלט 20 ו-50, לא ניתן לקבוע כי יש שוני באיכות הפתרון בין שני האלגוריתמים. לעומת זאת בגודלי קלט 100 ו-200, ניתן לקבוע כי אכן קיים שוני. בעקבות ממצאים אלו ביצענו השוואה נוספת בגודלי קלט 100 ו-200 אך שינינו את המבחן להיות מבחן חד-צדדי, מתוצאות הניסוי ניתן לקבוע כי התכנות לינארי מניב פתרון איכותי יותר.

תקציר באנגלית