|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy Iassenev 2:5020/400 07 May 2003 19:40:07
To : Domashenko Alexey
Subject : Re: Задача календарного планирования
--------------------------------------------------------------------------------
> Hello, All!
>
> Помогите решить задачку. Hужна идея!
> Есть 5 аппаратов. Hужно распланировать их
> ремонт в течении 8 недель.
> Каждый аппарат нужно ремонтировать 3 недели.
> Затраты труда на ремонт каждого аппарата из таблицы:
>
> Таблица:
> Hомер недели.....1.2.3..Hомер недели......Hомер недели
> (по порядку)..................раннего начала..позднего начала
> Hомер апп-та......................ремонта.................ремонта
> ..........1.................. 4 7
3.............1..........................4
> ..........2.................. 3 1
5.............1..........................3
> ..........3.................. 6 1
1.............2..........................5
> ..........4 ................. 2 3
6.............2..........................6
> ..........5................. .5 2
4.............3..........................5
> Т.е. ремонт 1 апп-та нужно начинать
> не раньше 1 недели и не позже 4 и т.д!
> Hужно минимизировать максимальное
> количество рабочей силы в течении любой недели!
Я в книге Седжвика читал, что задача календарного планирования сводится к
задаче нахождения всех длиннейших путей в графе. Сегодня посмотрю дома и
завтра напишу подробнее.
С уважением,
Дмитрий Ясенев.
P.S. Конечно, эту задачу можно решить и с помощью методов линейного
программирования, о которых уже было сказано, но реализация поиска путей и
проще, и будет быстрее работать, хотя для данной задачи оба алгоритма должны
отработать мгновенно.
--- ifmail v.2.15dev5
* Origin: Unknown (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
