(14/06/2024) עלו היום לאתר 9 סמינריונים 2 תזות 2 מאמרים

לרכישה גלול למטה לסוף הדוגמית

יישום יעיל של אלגוריתם 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 תקופות עם ביקוש ידוע image1 107, עלות הזמנה image2 103, עלות רכישה C, עלות החזקה H, בתקופה t. בעיית תזמון הייצור היא הבעייה של תזמון רכש בכל תקופה כדי לקיים ביקוש ולמזער את העלות.

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

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

image30 4

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

image4 83

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

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

הקדמה

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

אלגוריתם Wagner-Whitin

נתבונן בטווח התכנון בן N תקופות עם ביקושים ידועים image11 12 . עלות הזמנה בתקופה t  היא image9 35, עלות רכישה של יחידה – image14 8, ועלות אחסון יחידה בסוף התקופה – image8 22. גודל המנה הנרכשת בתקופה t הוא image20 9. Wagner and Whitin [8] הראו כי למדיניות אופטימלית מתקיים image22 7 כאשר image7 44 המלאי מוחזק בסוף התקופה image18 7. מהתוצאה נובע כי אנו צריכים רק פתרונות עבורם מתקיים image17 4 ל- k כלשהו.

יהי

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

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

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

image23 6

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

image36 2

עם image27 4 מוגדר כ- 0.

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

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

יישום

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

image40 6

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

image37 5

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

image31 4

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

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

image52 3

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

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

image57 2

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

image53 1

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

image60

לכן image62 2.

image63 1

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

image55

לכן image61.

image68 2

לכן image69 3.

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

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

image66 1

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

image65 1

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

סיכום

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

נספח

תוכנה ב-FORTRAN

……………………….

 

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

פברואר, 1985

JAMES R. EVANS*

* University of Cincinnati, Cincinnati, Ohio

 

תקציר מנהלים

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

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

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

image30 4

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

image4 83

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

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

הקדמה

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

295.00 

מק"ט b0a57707923d קטגוריה
מק"ט b0a57707923d קטגוריה

295.00 

סיוע בכתיבת עבודה מקורית ללא סיכונים מיותרים!

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