ארכון הבוגרים ביה"ס למנהל עסקים

לוח אירועים שנתי

א
ב
ג
ד
ה
ו
ש
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
דצמבר 2019
 

פרופ׳ גור מושיוב - בעיות תזמון וסידורי עבודה אופטימליים

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

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

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

לעוד פרטים על האלגוריתם, על הכללות של הבעיה ועל מחקרים נוספים בתחום אפשר לפנות למאמר:

"Scheduling with a due-window for acceptable lead-times" או לאתר של פרופ' מושיוב.

הוסף תגובה