תהליכי רשת

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

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

אילוץ מרכזי בזרימה ברשת הוא שלכל קשת יש קיבולת – הכמות המרבית שניתן להעביר בכל קשת בפרק זמן קבוע.

הבעיה בזרימה המקסימלית היא קביעת הסכום הכולל שאפשר להעביר בכל הקשתות ברשת, בהתאם למגבלות הקיבולת.

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

OR-Tools מספקת מספר פותרים לבעיות בזרימת הרשת בספריות התרשים שלה.

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

• מספר מקסימלי של תהליכי עבודה
• זרימת עלויות מינימלית
• הקצאה כזרימה של עלות מינימלית
• הקצאה עם צוותים של עובדים