1 Тема от Roman

  • Roman
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-23
  • Сообщений: 1

Тема: Ограничения и Задача Джонсона при N = 1

Всем привет, у меня вопрос насколько будет отличаться решение задачи Джонсона при N=1, если ещё ввести ограничения по времени на обработку каждой детали т.е. добавить ещё один массив в котором будут крайние сроки  времена после истечения которых начисляется штраф ссылка на сам алгоритм вот http://e-maxx.ru/algo/johnson_problem_1

2 Ответ от e-maxx

  • e-maxx
  • admin
  • Неактивен
  • Откуда: Саратов
  • Зарегистрирован: 2009-06-10
  • Сообщений: 360

Re: Ограничения и Задача Джонсона при N = 1

Есть ощущение, что отличаться будет весьма сильно smile Если раньше у нас была просто сортировка с хитрым компаратором, то теперь в неё надо как-то внести эти времена, что кажется нерешаемой задачей.

Сайтe-maxx

3 Ответ от cmd

  • cmd
  • Участник
  • Неактивен
  • Откуда: Волжский
  • Зарегистрирован: 2009-06-11
  • Сообщений: 35

Re: Ограничения и Задача Джонсона при N = 1

Ну впринципе ниже написано, что:
Теорема Лившица-Кладова

Теорема Лившица-Кладова утверждает, что перестановочный приём применим для следующих функций штрафа и только для них:

    * Fi(t) = Ci t + Bi
    * Fi(t) = Ci eA t + Bi, где A > 0
    * Fi(t) - монотонно возрастающие функции
А какие функции получаются: Fi(t) = (t > Deadline_i) * штраф_i, то они монотонно возрастающие, что вроде бы подходит.