Как получить кратчайшее время из последовательности работ?

Question

Я программирую на проблему управления процессами.Скажем, есть последовательность работ, которые нужно выполнять по очереди, вы должны закончить работу1 перед работой2 для каждого элемента.Используйте следующий пример:

work1   8   6   2   4
work2   3   1   3   12

нам нужно использовать 8 часов для завершения работы1 для первого столбца и еще 3 часа, но если мы закончим столбец 4 сначала, в течение следующих 12 часов, у нас есть некоторыевремя сделать столбец 3 и столбец 2. Лучше поставить этот столбец на первом шаге.

Моя интуитивная идея, work2 - это узкое место, то есть нам нужно использовать 3 + 1 + 3 +12 = 20 по крайней мере, чтобы закрыть эту сделку.Это значит, что процесс work2 всегда должен работать как можно больше.Мой алгоритм: обратная сортировка work2 и сортировка work1, так как мы хотим, чтобы процесс work2 был максимально занят.

Это мои алгоритмы, похоже, что они работают:

class Solution(object):
    def least_time(self, intervals):
        intervals.sort(key = lambda x: (-x[1], x[0]))
        time1 = time2 = 0 
        print intervals
        for inv in intervals:
            item1, item2 = inv
            if time1 + item1 <= time2 + item2:
                time1 += item1 
                time2 += item2
            else:
                time1 += item1
                time2 = time1 + item2

        return time2


if __name__ == "__main__":
    s = Solution()
    invs = [(8,3), (6,1), (2,3), (4,12)]
    print(s.least_time(invs))




>>>[(4, 12), (2, 3), (8, 3), (6, 1)]
>>>21

Умеет закончить вещь в указанном порядке в течение 21 часа.

Мой вопрос: 1. Верны ли мои алгоритмы?2. Как расширить эту проблему работает?(работа1 -> работа2 -> работа3 -> ...-> работа)

Answer 1

Я привел пример ниже, но я думаю, что веб-поиск найдет ответы, которые вы действительно хотите.

Для случая с двумя машинами проблему можно решить (https://en.wikipedia.org/wiki/Job_shop_scheduling#Jobs_consisting_of_multiple_operations) сПравило Джонсона (https://en.wikipedia.org/wiki/Johnson%27s_rule).

. Поскольку в первом упоминании говорится о постановке правила Джонсона на случай более двух машин, я полагаю, что для этого случая не существует другого более удовлетворительного решения.

Предположим, что у вас есть сочетание двух видов заданий: одно - два шага, а затем - три шага B. Другое - три шага, а два шага - B. Один шаблон, который, кажется, работает, чередует два задания.занят в течение двух этапов с незанятым B. Затем B выполняет это задание в течение трех этапов, в то время как A выполняет другое задание. В конце этого времени A вручает B задание, для которого B выполнялось три шага за два, пока Aберет на себя первый вид работы.

Таким образом, оба постоянно заняты, чередуя два-три шага на задание.

Не думаю, что это получитсяВаш алгоритм предварительной сортировки.

Один общий (но очень дорогой в вычислительном отношении) алгоритм будет использовать поиск A * с эвристикой, которая говорит, что время для завершения из определенного состояния было максимальным (время, затрачиваемое на Aесли постоянно занят, время, занятое B, если постоянно занят).Существует большая литература по проблемам планирования, которой, к сожалению, у меня в голове нет - я просто знаю, что она существует, и что большинство нетривиальных проблем оказывается NP-полными.