МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” КАФЕДРА ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ Звіт До лабораторної роботи № 2 На тему: “ Побудова розкладу роботи обладнання виробничої системи ” З дисципліни : "Моделювання програмного забезпечення" Мета роботи: побудувати розклад роботи обладнання виробничої системи. Завдання: Виробнича система складає m верстатів, настроєних на виконання певної технологічної операції. На обробку надходить n партій заготовок з однаковими технологічними маршрутами, що передбачають обробку заготовок на всіх m верстатах. Для заданих у варіанті значень m і n, а також матриці T=tij нормативних значень часу на виконання операцій побудувати розклад роботи обладнання виробничої системи двома способами: а) повним перебором всіх можливих послідовностей виконання робіт, що надійшли на обробку; б) за алгоритмом Дудека. Розклад оптимізувати за критерієм мінімуму затрат часу на виконання всіх робіт. Код програми using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; namespace Lab2_MPZ { public partial class Form1 : Form { public int[,] InputTimeAllocation; public int[][] Sequence; public class TimePosition { public int Value; public int Row; public int Column; public TimePosition(int Time, int x, int y) { Value = Time; Row = x; Column = y; } } public class TimePositionComparer : IComparer<TimePosition> { #region IComparer<TimePosition> Members public int Compare(TimePosition x, TimePosition y) { if (x.Value == y.Value) return 0; if (x.Value < y.Value) return -1; if (x.Value > y.Value) return 1; return x.ToString().CompareTo(y.ToString()); } #endregion } public Form1() { InitializeComponent(); dataGridView1.Rows.Add(); dataGridView1.Rows.Add(); dataGridView1.Rows.Add(); dataGridView1.Rows.Add(); dataGridView1.Rows[0].Cells[0].Value = "14"; dataGridView1.Rows[0].Cells[1].Value = "8"; dataGridView1.Rows[0].Cells[2].Value = "3"; dataGridView1.Rows[0].Cells[3].Value = "1"; dataGridView1.Rows[0].Cells[4].Value = "2"; dataGridView1.Rows[1].Cells[0].Value = "3"; dataGridView1.Rows[1].Cells[1].Value = "6"; dataGridView1.Rows[1].Cells[2].Value = "10"; dataGridView1.Rows[1].Cells[3].Value = "5"; dataGridView1.Rows[1].Cells[4].Value = "1"; dataGridView1.Rows[2].Cells[0].Value = "1"; dataGridView1.Rows[2].Cells[1].Value = "4"; dataGridView1.Rows[2].Cells[2].Value = "6"; dataGridView1.Rows[2].Cells[3].Value = "3"; dataGridView1.Rows[2].Cells[4].Value = "3"; dataGridView1.Rows[3].Cells[0].Value = "6"; dataGridView1.Rows[3].Cells[1].Value = "20"; dataGridView1.Rows[3].Cells[2].Value = "3"; dataGridView1.Rows[3].Cells[3].Value = "5"; dataGridView1.Rows[3].Cells[4].Value = "6"; InputTimeAllocation = new int[dataGridView1.RowCount - 1, dataGridView1.ColumnCount]; } private void DudecCount_Click(object sender, EventArgs e) { InputTimeAllocation = new int[dataGridView1.RowCount - 1, dataGridView1.ColumnCount]; // зчитування даних з таблиці for (int i = 0; i < dataGridView1.RowCount - 1; i++) for (int j = 0; j < dataGridView1.ColumnCount; j++) try { InputTimeAllocation[i, j] = int.Parse((string)dataGridView1.Rows[i].Cells[j].Value); } catch { MessageBox.Show(string.Format("Помилка при вводі даних в комірку ({0}, {1})", i, j)); return; } int MachineCount = InputTimeAllocation.GetLength(1); int DetailCount = InputTimeAllocation.GetLength(0); List<Point>[] JonsonInput = new List<Point>[MachineCount - 1]; for (int i = 0; i < (MachineCount - 1); i++) JonsonInput[i] = new List<Point>(); // генеруємо вхідні дані для задачі Джонсона з двома верстатами for (int i = 0; i < (MachineCount - 1); i++) for (int j = 0; j < DetailCount; j++) { int A = 0; int B = 0; for (int k = 0; k <= i; k++) { A += InputTimeAllocation[j, k]; B += InputTimeAllocation[j, MachineCount - k - 1]; } JonsonInput[i].Add(new Point(A, B)); } #region Метод Джонсона для двох машин для MachineCount-1 випадків int OptionIndex = 0; int[][] result = new int[MachineCount - 1][]; int[] result_time = new int[MachineCount - 1]; for (int i = 0; i < (MachineCount - 1); i++) { result[i] = new int[DetailCount]; } do { List<TimePosition> TimeAllocation = new List<TimePosition>(); for (int i = 0; i < DetailCount; i++) { TimeAllocation.Add(new TimePosition(JonsonInput[OptionIndex][i].X, i, 0)); TimeAllocation.Add(new TimePosition(JonsonInput[OptionIndex][i].Y, i, 1)); } TimeAllocation.Sort(new TimePositionComparer()); bool[] used = new bool[DetailCount]; List<int>[] result_tmp = new List<int>[2]; result_tmp[0] = new List<int>(); result_tmp[1] = new List<int>(); for (int i = 0; i < 2 * DetailCount; i++) { if (!used[TimeAllocation[i].Row]) { used[TimeAllocation[i].Row] = true; result_tmp[TimeAllocation[i].Column].Add(TimeAllocation[i].Row); } } result_tmp[0].CopyTo(result[OptionIndex]); result_tmp[1].Reverse(); result_tmp[1].CopyTo(result[OptionIndex], result_tmp[0].Count); #region Обрахунок часу роботи лінії int timeA = 0, timeB = 0; for (int i = 0; i < DetailCount; i++) { int curr_pos = result[OptionIndex][i]; timeA += JonsonInput[OptionIndex][curr_pos].X; if (timeB < timeA) timeB = timeA; timeB += JonsonInput[OptionIndex][curr_pos].Y; } if (timeA > timeB) result_time[OptionIndex] = timeA; else result_time[OptionIndex] = timeB; #endregion OptionIndex++; } while (OptionIndex < (MachineCount - 1)); #endregion int MinTime = int.MaxValue; int MinIndex = 0; for (int i = 0; i < result_time.Length; i++) { if (result_time[i] < MinTime) { MinTime = result_time[i]; MinIndex = i; } } MinTime = WorkingTimeCounting(InputTimeAllocation, result[MinIndex]); label1.Text = string.Format("Мінімальні затрати по часу для обробки всіх деталей складуть {0} сек\r\nпри такій послідовності обробки деталей:\r\n", MinTime); foreach (int t in result[MinIndex]) label1.Text = label1.Text + string.Format("{0}, ", (t + 1).ToString()); Sequence = new int[result.GetLength(0)][]; listBox2.Items.Clear(); for (int i = 0; i < result.Length; i++) { Sequence[i] = result[i]; StringBuilder sb = new StringBuilder(); foreach (int t in result[i]) sb.AppendFormat("{0}, ", t+1); sb.AppendFormat(" {0} сек", WorkingTimeCounting(InputTimeAllocation, result[i])); listBox2.Items.Add(sb.ToString()); } /* MachineCount = 2; int[,] DrawInput = new int[DetailCount, MachineCount]; for (int i = 0; i < DetailCount; i++) { DrawInput[i, 0] = JonsonInput[MinIndex][i].X; DrawInput[i, 1] = JonsonInput[MinIndex][i].Y; } */ WorkGraphicDrawing(InputTimeAllocation, result[MinIndex], MinTime, pictureBox1); } public int WorkingTimeCounting(int[,] InputTimeAllocation, int[] Sequence) { #region Обрахунок часу роботи лінії для основної задачі int DetailCount = InputTimeAllocation.GetLength(0); int MachineCount = InputTimeAllocation.GetLength(1); int[] Time = new int[MachineCount]; // загальний час роботи кожного верстата int time; for (int i = 0; i < DetailCount; i++) for (int j = 0; j < MachineCount; j++) { time = InputTimeAllocation[Sequence[i], j]; Time[j] += time; for (int k = j + 1; k < MachineCount; k++) if (Time[j] - Time[k] > 0) Time[k] += Time[j] - Time[k]; } return Time.Max(); #endregion } public void WorkGraphicDrawing(int[,] DrawInput, int[] Sequence, double TotalTime, PictureBox PB) { #region малювання графіка завантженості PB.Refresh(); // зчитуємо вихідні дані Graphics gr = Graphics.FromHwnd(PB.Handle); int X0 = 30; int Y0 = PB.Height - 20; int GraphicWidth = PB.Width - 20 - X0; int GraphicHeigth = PB.Height - 20 - Y0; int DetailCount = DrawInput.GetLength(0); int MachineCount = DrawInput.GetLength(1); // малюємо осі координат gr.DrawLine(new Pen(Color.Black, 2), X0, 20, X0, Y0); gr.DrawLine(new Pen(Color.Black, 2), X0, Y0, GraphicWidth + X0, Y0); gr.DrawString("T", new Font("Arial", 14), Brushes.BlueViolet, X0 + GraphicWidth - 10, Y0 + 5); // рахуємо висоту на якій буде знаходитися відповідна лінія кожного верстату int[] HeightX = new int[MachineCount]; for (int i = 1; i <= MachineCount; i++) { HeightX[i - 1] = (PB.Height / (MachineCount + 1)) * i; gr.DrawString("В " + i.ToString(), new Font("Arial", 10), Brushes.Fuchsia, X0 - 30, HeightX[i - 1] - 7); } // генеруємо кольори для кожної деталі Color[] DetailsColor = new Color[DetailCount]; Random rand = new Random((int)DateTime.Now.Ticks); for (int i = 0; i < DetailCount; i++) { DetailsColor[i] = new Color(); DetailsColor[i] = Color.FromArgb(rand.Next(255), rand.Next(255), rand.Next(255)); } int[] MachineXPosition = new int[MachineCount]; // позиції графіків для кожного верстата int[] MachineStandTime = new int[MachineCount]; // простої кожного верстата int[] Time = new int[MachineCount]; // загальний час роботи кожного верстата int time; // обраховуємо масштаб графіка double scale = (GraphicWidth-15) / TotalTime; Pen DashPen = new Pen(Color.Silver, 2); // перо для пунктирної лінії DashPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Dash; // малюємо сам графік for (int i = 0; i < DetailCount; i++) { for (int k = 0; k < MachineCount; k++) { time = DrawInput[Sequence[i], k]; Time[k] += time; for (int j = k + 1; j < MachineCount; j++) { if ((int)(time * scale) + MachineXPosition[k] - MachineXPosition[j] > 0) { MachineXPosition[j] += ((int)(time * scale) + MachineXPosition[k] - MachineXPosition[j]); Time[j] += Time[k] - Time[j]; } } gr.DrawLine(new Pen(DetailsColor[Sequence[i]], 5), MachineXPosition[k] + X0 + (int)(MachineStandTime[k] * scale), HeightX[k], MachineXPosition[k] + (int)(time * scale) + (int)(MachineStandTime[k] * scale) + X0, HeightX[k]); gr.DrawLine(DashPen, MachineXPosition[k] + (int)(time * scale) + X0, HeightX[k], MachineXPosition[k] + (int)(time * scale) + X0, Y0); gr.DrawString(Time[k].ToString(), new Font("Arial", 10), new SolidBrush(DetailsColor[Sequence[i]]), MachineXPosition[k] + (int)(time * scale) + X0 - 10, Y0 + 7); MachineXPosition[k] += (int)(time * scale) + (int)(MachineStandTime[k] * scale); } } #endregion } private void ColumnCounter_ValueChanged(object sender, EventArgs e) { if (dataGridView1.Columns.Count == ColumnCounter.Value) return; if (dataGridView1.Columns.Count < ColumnCounter.Value) { for (int i = dataGridView1.Columns.Count; i < ColumnCounter.Value; i++) dataGridView1.Columns.Add("Column" + (i+1).ToString(), ""); } if (dataGridView1.Columns.Count > ColumnCounter.Value) { for (int i = (int)ColumnCounter.Value; i < dataGridView1.Columns.Count; ) dataGridView1.Columns.Remove("Column" + dataGridView1.Columns.Count.ToString()); } } #region Ф-ції для генерації перестановок private double Factor(double n) { if (n <= 1) return 1; else return n * Factor(n - 1); } private void Swap(ref int a, ref int b) { int t; t = a; a = b; b = t; } private void Reverse(ref int[] P, int m) { int i = 0, j = m; while (i < j) { Swap(ref P[i], ref P[j]); ++i; --j; } } private void Antilex(ref int[] P, int m, ref int[][] Result, ref int index) { int i; int N = P.GetLength(0); if (m == 0) { for (i = 0; i < N; ++i) Result[index][i] = P[i]; index++; } else { for (i = 0; i <= m; ++i) { Antilex(ref P, m - 1, ref Result, ref index); if (i < m) { Swap(ref P[i], ref P[m]); Reverse(ref P, m - 1); } } } } #endregion private void BruteForseMethod_Click(object sender, EventArgs e) { InputTimeAllocation = new int[dataGridView1.RowCount - 1, dataGridView1.ColumnCount]; // зчитування даних з таблиці for (int i = 0; i < dataGridView1.RowCount - 1; i++) for (int j = 0; j < dataGridView1.ColumnCount; j++) try { InputTimeAllocation[i, j] = int.Parse((string)dataGridView1.Rows[i].Cells[j].Value); } catch { MessageBox.Show(string.Format("Помилка при вводі даних в комірку ({0}, {1})", i, j)); return; } int MachineCount = InputTimeAllocation.GetLength(1); int DetailCount = InputTimeAllocation.GetLength(0); int N = (int)Factor(DetailCount); int[] P = new int[DetailCount]; for(int i=0; i<DetailCount; ++i) P[i] = i; Sequence = new int[N][]; for(int i=0; i<N; i++) Sequence[i] = new int[DetailCount]; int index = 0; Antilex(ref P, DetailCount - 1, ref Sequence, ref index); int[] Time = new int[N]; int MinTime = int.MaxValue; int MinIndex = 0; for (int i = 0; i < N; i++) { Time[i] = WorkingTimeCounting(InputTimeAllocation, Sequence[i]); if (Time[i] < MinTime) { MinTime = Time[i]; MinIndex = i; } } label3.Text = string.Format("Мінімальні затрати по часу для обробки всіх деталей складуть {0} сек\r\nпри такій послідовності обробки деталей:\r\n", MinTime); foreach (int t in Sequence[MinIndex]) label3.Text = label3.Text + string.Format("{0}, ", (t + 1).ToString()); WorkGraphicDrawing(InputTimeAllocation, Sequence[MinIndex], MinTime, pictureBox2); listBox1.Items.Clear(); for (int i = 0; i < N; i++) { StringBuilder sb = new StringBuilder(); foreach(int t in Sequence[i]) sb.AppendFormat("{0}, ",t+1); sb.AppendFormat(" {0} сек",WorkingTimeCounting(InputTimeAllocation,Sequence[i])); listBox1.Items.Add(sb.ToString()); } } private void listBox1_Click(object sender, EventArgs e) { WorkGraphicDrawing(InputTimeAllocation, Sequence[listBox1.SelectedIndex], WorkingTimeCounting(InputTimeAllocation,Sequence[listBox1.SelectedIndex]), pictureBox2); } private void listBox2_Click(object sender, EventArgs e) { WorkGraphicDrawing(InputTimeAllocation, Sequence[listBox2.SelectedIndex], WorkingTimeCounting(InputTimeAllocation, Sequence[listBox2.SelectedIndex]), pictureBox1); } } } Результат виконання завдання: Висновок: в даній роботі я навчився будувати розклад роботи обладнання виробничої системи методами Дудека та повним перебором всіх можливих послідовностей виконання робіт, що надійшли на обробку. Обчислення проводились за такими вхідними даними: кількість верстатів, настроєних на виконання певної технологічної операції, кількість партій заготовок з однаковими технологічними маршрутами, що передбачають обробку заготовок на всіх m верстатах, а також матриці T=tij нормативних значень часу на виконання операцій.