מתמטיקה בדידה עבור WMS: אלגוריתם לדחיסת סחורות בתאים (חלק 1)

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

אם אתה מעוניין ביישומים של מתמטיקה בעסקים ואינך חושש מתמורות זהות נוקשות של נוסחאות ברמת כיתה ה', אז ברוך הבא לחתול!

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

חלק מבוא

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

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

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

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

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

תיאור הבעיה בפתרון במחסן הלקוח

צוואר בקבוק בתהליכים

בשנת 2018 השלמנו פרויקט ליישום WMS-מערכות במחסן "בית המסחר "LD" בצ'ליאבינסק. הטמענו את המוצר "1C-Logistics: Warehouse Management 3" עבור 20 מקומות עבודה: מפעילים WMS, מחסנאים, נהגי מלגזות. המחסן הממוצע הוא כ-4 מ"ר, מספר התאים הוא 2 ומספר מק"ט הוא 5000. המחסן מאחסן שסתומים כדוריים מייצור עצמי בגדלים שונים החל מ-4500 ק"ג ועד 1 ק"ג. המלאי במחסן מאוחסן בקבוצות, שכן יש צורך בבחירת סחורה לפי FIFO.

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

איור 1. תמונה של כמה חלקים בתא

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

רעיון לפתרון בעיה

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

איור 2. תכנית לדחיסת שאריות בתאים

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

תהליך פתרון בעיה כזו מחולק ל-2 שלבים:

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

במאמר הנוכחי נתמקד בשלב השני של האלגוריתם.

סקירת פתרונות קיימים

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

קודם כל, יש לשים לב למוצר "1C: Enterprise 8. WMS Logistics. מחסן ניהול 4", שבבעלות ומשוכפל של 1C ושייך לדור הרביעי WMS-מערכות שפותחו על ידי AXELOT. מערכת זו טוענת לפונקציונליות דחיסה, שנועדה לאחד שרידי מוצרים שונים בתא משותף אחד. ראוי להזכיר שפונקציונליות הדחיסה במערכת כזו כוללת גם אפשרויות נוספות, למשל תיקון מיקום הסחורה בתאים לפי מחלקות ה-ABC שלהם, אך לא נתעכב עליהם.

אם תנתח את הקוד של מערכת 1C: Enterprise 8. WMS Logistics. ניהול מחסן 4" (שפתוח בחלק זה של הפונקציונליות), נוכל להסיק את הדברים הבאים. אלגוריתם הדחיסה השיורית מיישם לוגיקה ליניארית פרימיטיבית למדי ולא ניתן לדבר על דחיסה "אופטימלית" כלשהי. מטבע הדברים, הוא אינו מספק קיבוץ מפלגות. מספר לקוחות שהטמיעו מערכת כזו התלוננו על תוצאות תכנון הדחיסה. לדוגמה, לעתים קרובות בפועל במהלך דחיסה התרחש המצב הבא: 100 יח'. מתוכנן להעביר את הסחורה הנותרת מתא אחד לתא אחר, שבו ממוקמת חתיכה אחת. סחורות, למרות שמבחינת צריכת זמן זה אופטימלי לעשות את ההיפך.

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

חפש מודל מתמטי של הבעיה

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

יש הרבה תאים , המכילים שרידים של כמה סחורות. בהמשך, נקרא לתאים כאלה תאים תורמים. בואו נסמן נפח הסחורה בתא $.

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

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

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

נתון מטריצה ​​של המרחקים הקצרים ביותר במטרים בין כל זוג תאים איפה и שייכים לסטים и בהתאמה.

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

סמן ב משתנה שלוקח את הערך 1 אם השאר הוא מהתא הועבר למכולה , ו-0 אחרת. הבה נסמן ב משתנה שלוקח את הערך 1 אם המיכל מכיל את הסחורה הנותרת, ו-0 אחרת.

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

תחת הגבלות

בסך הכל, בעת חישוב הפתרון לבעיה, אנו שואפים:

• ראשית, כדי לחסוך בקיבולת אחסון;
• שנית, כדי לחסוך זמן למחסנאים.

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

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

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

אתה צריך למצוא באילו ערים לפתוח עסקים וכיצד לצרף לקוחות לעסקים כאלה כדי:

• סך העלויות של פתיחת מפעלים ועלויות ההובלה היו מינימליות;
• היקף הביקוש מלקוחות שהוקצו לכל מפעל פתוח לא עלה על כושר הייצור של אותו מיזם.

כעת ראוי להזכיר את ההבדל היחיד בשתי הבעיות הקלאסיות הללו:

• בעיית מיקום מתקן בעל יכולות מקור יחיד - הלקוח מקבל אספקה ​​ממתקן פתוח אחד בלבד;
• בעיית מיקום מתקן קיבול רב מקורות - ניתן לספק ללקוח ממספר מתקנים פתוחים בו-זמנית.

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

איור 3. א) בעיית מיקום מתקן קיבול רב מקורות

איור 3. ב) בעיית מיקום מתקן בעל מקור יחיד

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

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

• ערי לקוחות הן תאים תורמים עם הסחורה שנותרה,
• ערי ייצור – תאי מיכל , שבו אמורים להיות ממוקמים שאריות מתאים אחרים,
• עלויות הובלה - עלויות זמן מחסנאי להעביר את נפח הסחורה מהתא התורם לתוך תא מיכל ;
• עלויות פתיחת עסק - עלויות בחירת מכולה , שווה לנפח תא המיכל , מוכפל במקדם מסוים לשמירת נפחים חופשיים (ערך המקדם הוא תמיד > 1) (ראה סעיף הכנת נתוני קלט).

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

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

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

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

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

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

הכנת נתוני קלט

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

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

• עובר מ в יקר יותר מאשר מעבר מ в , שכן ירידה מהדרג השני (1,5-2 מטר מהרצפה) קלה יותר מלעלות לשני, אם כי המרחק יהיה זהה;
• העבר 1 מחשב. סחורה מהתא в זה יהיה קל יותר מאשר להעביר 10 חלקים. אותו מוצר, אם כי המרחק יהיה זהה.

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

תן מהתא מהלכים PC. סחורה במכולה ... תן להיות – מהירות התנועה הממוצעת של עובד במחסן, נמדדת ב-m/sec. לתת и – מהירויות ממוצעות של פעולות חד פעמיות קח והנחת, בהתאמה, עבור נפח סחורה השווה ל-4 dm3 (הנפח הממוצע שעובד לוקח בכל פעם במחסן בעת ​​ביצוע פעולות). לתת и גובה התאים שמהם מתבצעות פעולות הטייק והנחת, בהתאמה. לדוגמה, הגובה הממוצע של הרובד הראשון (קומה) הוא 1 מ', הרובד השני הוא 2 מ' וכו'. ואז הנוסחה לחישוב הזמן הכולל להשלמת פעולת העברה היא הַבָּא:

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

שם הפעולה	ייעוד	מתכוון
מהירות ממוצעת של עובד מסתובב במחסן		1,5 מ'/שניה
מהירות ממוצעת של פעולה אחת לשים (עבור נפח מוצר של 4 dm3)		2,4 שניות

טבלה 2. זמן ממוצע להשלמת פעולות המחסן

החלטנו על השיטה לחישוב עלויות המעבר. עכשיו אנחנו צריכים להבין איך לחשב עלויות בחירת תא מיכל. הכל כאן הרבה הרבה יותר מסובך מאשר בעלויות הובלה, כי:

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

אורז. 4. אפשרויות להעברת שאריות למיכלים בעלי יכולות שונות.

איור 4 מציג באדום את נפח השאריות שכבר לא נכנס למיכל בשלב השני של הצבת הסחורה הבאה.

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

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

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

נשאלת השאלה: מה הרווח המינימלי בנפח מקובל, עבור ערך אובדן זמן נתון ? בואו נסביר עם דוגמה. בתחילה, השרידים היו אמורים להיות מונחים במיכל בנפח של 1000 דמ"ק (3 מ"ק) וזמן ההעברה היה 1 שניות. ישנה אפשרות להניח את השאריות במיכל אחר בנפח 3 dm70 ובזמן של 500 שניות. שאלה: האם אנחנו מוכנים להשקיע 3 שניות נוספות מזמנו של המחסנאי בהעברת הסחורה כדי לחסוך 130 dm60 של נפח פנוי? בהתבסס על תוצאות סקר של עובדי המחסן, נערך התרשים הבא.

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

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

באיור שלהלן, אנו רואים את השיטות הבאות להנחת סחורות במכולות.

אורז. 6. אפשרות (א): 2 מיכלים, נפח כולל 400 dm3, זמן כולל 150 שניות.

אורז. 6. אפשרות (ב): 2 מיכלים, נפח כולל 600 dm3, זמן כולל 190 שניות.

אורז. 6. אפשרות (ג): מיכל 1, נפח כולל 400 dm3, זמן כולל 200 שניות.

אפשרות (א) לבחירת מכולות עדיפה יותר מהאופציה המקורית, שכן אי השוויון מתקיים: (800-400)/10>=150-120, מה שמרמז על 40 >= 30. אפשרות (ב) עדיפה פחות מהמקורית אפשרות , שכן אי השוויון לא מתקיים: (800-600)/10>=190-150 מה שמרמז על 20 >= 40. אבל אפשרות (ג) לא מתאימה להיגיון כזה! הבה נשקול אפשרות זו ביתר פירוט. מצד אחד, אי השוויון (800-400)/10>=200-120, כלומר אי השוויון 40 >= 80 אינו מסופק, מה שמרמז שהרווח בנפח אינו שווה הפסד כה גדול בזמן.

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

שינוי אי השוויון לעיל, אנו מקבלים

על סמך זה, יש לנו נוסחה לחישוב העלות הכוללת פתרון כלשהו לבעיה:

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

לתת – המרחק המרבי בין תאי המחסן של אזור אחד ABC, שווה במקרה שלנו ל-100 מ'. – הנפח המרבי של תא מיכל במחסן, שווה במקרה שלנו ל-1000 dm3.

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

שממנו נובע

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

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

שינוי אי השוויון שאנו מקבלים

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

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

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

מסקנה

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

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

הכין את הכתבה
רומן שנגין, מתכנת מחלקת הפרויקטים,
חברת First Bit, צ'ליאבינסק

מקור: www.habr.com