Решатель схемы кратчайшего потока

У меня есть последовательность маршрутизации для набора машин на сборочной линии. Каждый маршрут должен проходить через всю линию (то есть, если вы запускаете только первую и вторую машину, вы все равно учитываете расстояние от второй до конца линии).

У меня есть шесть разных машин (720 возможных комбинаций машин) с фиксированными расстояниями между каждым местом на линии. Расстояние между первой и второй машиной составляет 100 футов, между второй и третьей — 75 футов, между третьей и четвертой — 75 футов, четвертой и пятой — 25 футов, а между пятой и шестой — 25 футов.

У меня есть 4 разных продукта, которые должны проходить по линии, и каждый из них имеет фиксированную маршрутизацию.

Моя проблема заключается в том, как настроить код vba или решатель, который позволит мне выполнить все возможные комбинации настройки линии и определить оптимальную настройку для этой линии? Любую машину можно разместить в любом месте, главное, чтобы это оптимизировало результат!

Четыре маршрута продукта:

A - B - C - D - F
A - C - B - D – E - F
A - F - E - D - C - B - A - F
A - C - E - B - D – F

optimization vba flow combinations solver
person m.car    schedule 17.09.2017    source источник
comment
Похоже, это подходит для: en.wikipedia.org/wiki/Dijkstra%27s_algorithm.   -  person Ryan Wildry    schedule 17.09.2017
comment
Думаю, проще всего было бы просто перебрать все возможные конфигурации (их всего 720) и выбрать лучшую. Я подозреваю, что формальная оптимизационная модель не так проста.   -  person Erwin Kalvelagen    schedule 17.09.2017
comment
это похоже на домашнее задание   -  person jsotola    schedule 17.09.2017
comment
если ваши машины расположены в последовательности ABCDEF, происходит ли реверсирование продукта между C и B во втором маршруте продукта?   -  person jsotola    schedule 18.09.2017

Ответы (1)


arrow_upward
0
arrow_downward

Перебор всех возможных комбинаций — если вам действительно это нужно — это работа для чего-то вроде алгоритма кучи, хотя я предпочитаю простой метод изменений:

Sub Evaluate(Lineup() As String)
'  dummy evaluation, just output the permutation
Dim OffCell As Long
For OffCell = LBound(Lineup, 1) To UBound(Lineup, 1)
    ActiveCell.Offset(0, OffCell).Value = Lineup(OffCell)
Next OffCell
ActiveCell.Offset(1, 0).Activate

End Sub

Sub AllPerms(Lineup() As String)
' Lineup is a 1-D array indexed at 1

Dim LSize As Long
Dim Shift() As Long
Dim Tot As Long
Dim Idx As Long
Dim Level As Long
Dim Change As Long
Dim Offset As Long
Dim TempStr As String

LSize = UBound(Lineup)
ReDim Shift(LSize)

'count of permutations, set initial changes
Tot = 1
For Idx = 2 To LSize
    Tot = Tot * Idx
    Shift(Idx) = 1 - Idx
Next Idx
Shift(1) = 2 ' end condition

' go through permutations
For Idx = 1 To Tot
    ' check this one
    Call Evaluate(Lineup)
    ' switch for the next
    Level = LSize
    Offset = 0
    Change = Abs(Shift(Level))
    Do While Change = 0 Or Change = Level
        If Change = 0 Then Shift(Level) = 1: Offset = Offset + 1
        If Change = Level Then Shift(Level) = 1 - Level
        Level = Level - 1
        Change = Abs(Shift(Level))
    Loop
    Shift(Level) = Shift(Level) + 1
    Change = Change + Offset
    TempStr = Lineup(Change)
    Lineup(Change) = Lineup(Change + 1)
    Lineup(Change + 1) = TempStr
Next Idx

End Sub

Sub ABCDEF_case()
Dim LU(6) As String
LU(1) = "A"
LU(2) = "B"
LU(3) = "C"
LU(4) = "D"
LU(5) = "E"
LU(6) = "F"

Call AllPerms(LU)
End Sub
person Joffan    schedule 17.09.2017