יישום יעיל של אלגוריתם Wagner-Whitin עבור תזמון הייצור An Efficient Implementation of the Wagner-Whitin Algorithm for Dynamic Lot-Sizing

יישום יעיל של אלגוריתם Wagner-Whitin עבור תזמון הייצור

פברואר, 1985

JAMES R. EVANS*

* University of Cincinnati, Cincinnati, Ohio

תקציר מנהלים

אנו חוקרים טווח תכנון בן N תקופות עם ביקוש ידוע , עלות הזמנה , עלות רכישה C, עלות החזקה H, בתקופה t. בעיית תזמון הייצור היא הבעייה של תזמון רכש בכל תקופה כדי לקיים ביקוש ולמזער את העלות.

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

חישוב רקורסיבי מנוסח כדלקמן:

כאן  עלות הנגרמת על ידי רכש בתקופה j בכל תקופה j לכל k, ו-  עלות מינימלית לכל התקופות מ-1 ל- k . היישומים  שלנו מסתמכים על התצפיות הבאות לגבי החישובים האלה:

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

התוכנהFORTRAN  שיושמה ב- Amdahl 470 חישבה במשך  (ב-  שניות). בעיות עם N = 500 פותרו  בפחות מ- 2 שניות.

הקדמה

החוקרים בניהול ייצור ומלאי במשך זמן רב התיחסו לאלגוריטת Wagner-Whitin [8] כאל גישה לא פרקטית בבעיות תזמון ייצור. ו-  [1], למשל, טועענים כי האלגוריטת Wagner-Whitin אינו מובן לאנשי תעשיה ודי יקר במונחים של זמן מחשבים וגודל הזיכרון. כתוצאה,שיטות היוריסטיות רבות הוצעו לבעיות תזמון ייצור [3, 4, 5, 7]. למרות שמחבר המאמר הזה מאמין חזק בשימוש מתאים בשיטות היוריסטיות, הוא גם סבור כי בשיטות האלה  לא כדאי להשתמש כאשר זמינים אלגוריתמים אופטימליים [9]. יתר על כן, מכיוון שהאלגוריתם Wagner-Whitin הוא שיטה עם המסלול הקצר ביותר ברשת עם מבנה מיוחד, הייתי קצת מבולבל בגלל הספקנות סביב השיטה. האלגוריתמים לבעיות של המסלול הקצר ביותר היו ידועים “כיעילים”, כלומר מוגבלים פולינומיאלית [2]. המחקר בעשור וחצי האחרון הראה כי אלגוריתמים רבים די רגישים ליישום ספציפי במחשב. לכן אנו האמינו כי את תוכנת המחשב היעילה לאלגוריתם Wagner-Whitin באמת אפשר היה לפתח. במאמר זה אנו מסלקים את המיתוסים לגבי אי-ישימות של האלגוריתם Wagner-Whitin ומציגים ישום יעיל עם דרישות נמוכות לזיכרון וזמן. זה הושג על ידי גישה חדשה לחישובים ושימוש במבנה מיוחד של הבעיה. כדי לעשות את ההצגה ברורה, אנו בהתחלה מציגים סקר הבעיה של תזמון ייצור ושל האלגוריתם  Wagner-Whitin.

אלגוריתם Wagner-Whitin

נתבונן בטווח התכנון בן N תקופות עם ביקושים ידועים  . עלות הזמנה בתקופה t  היא , עלות רכישה של יחידה – , ועלות אחסון יחידה בסוף התקופה – . גודל המנה הנרכשת בתקופה t הוא . Wagner and Whitin [8] הראו כי למדיניות אופטימלית מתקיים  כאשר  המלאי מוחזק בסוף התקופה . מהתוצאה נובע כי אנו צריכים רק פתרונות עבורם מתקיים  ל- k כלשהו.

יהי

 = כחות מינימלית לתקופות מ-1 ל-k  כאשר

 = עלות ייצור בתקופה j לכל תקופות j ולכל k, כלומר כאשר .

אם כן,  פשוט סכום של ערכי . אנו יכולים לרשום

עלות מינימלית לתקופות מ- 1 ל- k יכולה להיות מוגדרת באופן רקורסיבי על ידי

עם  מוגדר כ- 0.

אופי רקורסיבי של החישובים מביא לרעיון עח תכנות דינמית. למרות שמשתמשים ב”עקרון האופטימליות” של תכנות דינמית, אנו מדגישים כי האלגוריתם  Wagner-Whitinאינו סובל מ- “קללת ממדיות” אשר מופיעה ברוב יישומים של תכנות דינמית, בגלל התכונה . אולי ההערה הזו מסבירה מדוע רבים האמינו כי האלגוריתם אינו פרקטי מבחינת החישובים.

אפשר לראות את הבעיה כהבעיה של המסלול הקצר ביותר ברשת. כל קודקוד מתאים לתקופת זמן, והקשת מקודקוד j לקודקוד k + 1 מציגה ייצור בתקופה j המקיים כל הדרישות לכל התקופות k עם העלויות שלהן . הדוגמה עם ארבע תקופות מוצגת באיור 1.  מציגה עלות של המסלול הקצר ביותר מקודקוד 1 לקודקוד k + 1.

יישום

היישום שלנו של האלגוריתם  Wagner-Whitinמתבסס על התצפיות הבאות:

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

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

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

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

בעזרת המושגים האלה, אנו צריכים רק 8 מערכים, כל אחד  באורך N; 4 לנתוני ,  , ואחד לכל אחד מ-  (אינו תלוי ב- k) , , המצביע לאינדקס j אשר ממזער , וסכומים מצטברים של עלויות החזקה. קוד FORTRAN של האלגוריתם (23 פקודות לא כולל כלט ופלט) מובא בנספח. הקוד מובן באליו, אולי פרט ל- JSTAR(k) בו נשמר האינדקס j אשר ממזער את .

כדי להמחיש את החישובים אנו מציגים את הדוגמה בת 4 תקופות אשר נלקחה מ- .הנתונים נתונים בטבלה 1. בהתחלה במשוואה (3) לחשב :

להלן נתונים התחלתיים ל- :

 מציגים סכום מצטבר של  ערכים [המשוואה (6)]. בהתחלה כל .

לכן .

טבלה 1. נתונים לבעיית הדוגמה.

לכן .

לכן .

בפתרון האופתימלי מייצרים 200 יחידות בתקופה 4, 240 יחחידות בתקופה 2, ו- 60 יחידות בתקופה 1.

טבלה 2. תוצאות חישובים.

איור 2. דרישות לחישובים ().

בטבלה 2 מוצגים תוצאות חישובים לבעיות שנבחרו באקראי עם עד ל-96 תקופות תכנון. הבעיות פותרו ב- . נציין כי בגלל שמספר החישובים הדרושים הוא פונקציה דטרמיניסטית של N, האלגוריתם אינו תלוי בנתונים. לכן אנו יכולים לחזות, ברמה גבוהה של דיוק, את הזמן הדרוש ל- N נתון. באיור 2 נראה עקום של זמן חישוב כפונקציה של N. בגלל שהאלגוריתם תיאורטים פולינומי ב- , הקירוב בעזרת רגרסיה פולינומיאלית מתבצעת ב-  עם דיוק קמעט מושלם. בעזרת המשוואה הזו, הבעייה עם 500 תקופות תדרוש כ- 1.127 שניות. ובהתאם לזה, פתרנו את הבעיה עם 500 תקופות ב- 1.213 שניות.

סיכום

פיתחנו יישום חזק של האלגוריתם Wagner-Whitin אשר אמור להיות טוב יותר משיטות היוריסטיות במונחי זמן חישוב. השיטה שלנו פשוטה וניתן בקלות ליישם אותה במיקרו מחשבים ולכלול אותה במערכות MRP. אנו מאמינים כי הגישה הזו יכולה להיות יעילה בתוכנות מחשב להרחבות שונות של הבעייה של תזמון ייצור.

נספח

תוכנה ב-FORTRAN

……………………….