223
правки
Изменения
Новая страница: «{{В разработке}} ==Постановка задачи== Задача <tex> P_2 \mid p_i = 1, prec, r_i \mid \sum C_i </tex> ([[Классификац...»
{{В разработке}}
==Постановка задачи==
Задача <tex> P_2 \mid p_i = 1, prec, r_i \mid \sum C_i </tex> ([[Классификация_задач|в нотации Грэхема]]).
Есть два станка и <tex> n </tex> работ. Любая работа выполняется за единицу времени. Для каждой работы задано число <tex> r_i </tex> {{---}} минимальное время, когда можно начать ее выполнять. Кроме того, определено отношение предшествования: если работа <tex> J_j</tex> предшествует работе <tex> J_k</tex>, то будем записывать так: <tex>J_j \prec J_k</tex> (что означает, что время начала выполнения работы <tex> J_k </tex> больше или равно времени завершения работы <tex> J_j </tex>). Записью <tex> J_j \preceq J_k </tex> будем обозначать, что либо <tex> j = k</tex> либо <tex>J_j \prec J_k</tex>.
Необходимо составить расписание, в котором сумма времени окончания работ <tex>\sum C_i</tex> будет минимальной.
==Некоторые замечания==
Заметим что введенное отношение предшествования необязательно должно быть [[Транзитивное_отношение|транзитивным]].
Начатая работа не может быть прервана. Таким образом понятно, что все времена начал и завершения работ будут целыми. По этой причине можно полагать, что все числа <tex> r_i </tex> тоже целые.
==Ссылки==
* [http://www.springerlink.com/content/8kr73f7n44m1mjtr/ Philippe Baptiste and Vadim G. Timkovsky "Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time" (2004)]
==Постановка задачи==
Задача <tex> P_2 \mid p_i = 1, prec, r_i \mid \sum C_i </tex> ([[Классификация_задач|в нотации Грэхема]]).
Есть два станка и <tex> n </tex> работ. Любая работа выполняется за единицу времени. Для каждой работы задано число <tex> r_i </tex> {{---}} минимальное время, когда можно начать ее выполнять. Кроме того, определено отношение предшествования: если работа <tex> J_j</tex> предшествует работе <tex> J_k</tex>, то будем записывать так: <tex>J_j \prec J_k</tex> (что означает, что время начала выполнения работы <tex> J_k </tex> больше или равно времени завершения работы <tex> J_j </tex>). Записью <tex> J_j \preceq J_k </tex> будем обозначать, что либо <tex> j = k</tex> либо <tex>J_j \prec J_k</tex>.
Необходимо составить расписание, в котором сумма времени окончания работ <tex>\sum C_i</tex> будет минимальной.
==Некоторые замечания==
Заметим что введенное отношение предшествования необязательно должно быть [[Транзитивное_отношение|транзитивным]].
Начатая работа не может быть прервана. Таким образом понятно, что все времена начал и завершения работ будут целыми. По этой причине можно полагать, что все числа <tex> r_i </tex> тоже целые.
==Ссылки==
* [http://www.springerlink.com/content/8kr73f7n44m1mjtr/ Philippe Baptiste and Vadim G. Timkovsky "Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time" (2004)]
