4. Простая задача планирования

Во введении к данной главе мы описали пример промышленной фирмы, выпускающей продукты с использованием единственного типа аппаратуры в циклическом режиме, и поставили вопрос о порядке производства продуктов, требующем наименьшего возможного числа перенастроек аппаратуры. Был построен граф вершины которого представляют продукты а дуги показывают, что продукт можно производить вслед за продуктом без перенастройки.

Если граф имеет гамильтонов цикл, например то соответствующая последовательность продуктов может быть произведена на аппаратуре без какой-либо перенастройки, так как по определению тамильтонова цикла

для всех определено выше как множество

Если не имеет никакого гамильтонова цикла, то мы можем построить граф где

и

т. е. ввести в граф фиктивную вершину вместе с дугами, ведущими в нее и исходящими из нее в каждую действительную вершину графа

Если у графа существует гамильтонов цикл, то он будет иметь вид что приводит к

следующей последовательности производства продуктов

с единственной операцией перенастройки после окончания производства последнего продукта и началом производства первого. Таким образом, фиктивная вершина играет роль метки, показывающей то место в последовательности, где необходима перенастройка аппаратуры. В терминах графа фиктивная вершина и ассоциированные с ней дуги обеспечивают существование цепи между двумя действительными вершинами. Таким образом, если существует последовательность продуктов с одной перенастройкой, т. е. если в существует гамильтонов цикл, при условии, что можно использовать одну «дугу» то добавление вершины всегда приведет к существованию в гамильтонова цикла, так как лишняя необходимая «дуга» может быть заменена двумя фиктивными дугами и

Если граф не имеет гамильтонова цикла, то мы построим граф вместо графа где

и

и аналогично будем действовать далее.

Теорема 1. Если граф определяемый как

содержит гамильтонов цикл, а граф такого цикла не содержит, то число есть минимальное число необходимых перенастроек, и если гамильтонов цикл в имеет вид

то продукты должны производиться в последовательности

Доказательство. Доказательство следует непосредственно из рассуждений, предшествующих теореме, с использованием индукции.

4.1. Вычислительные аспекты

В рассуждениях предыдущего раздела граф каждый раз пополнялся единственной фиктивной вершиной. Если оптимальное решение задачи содержит перенастроек аппаратуры, то нужно будет сделать попыток отыскать гамильтоновы циклы в графах причем только последняя из этих попыток окажется успешной и приведет к решению задачи. Очевидно, что число ограничено сверху величиной пив общем случае в практических задачах оно будет лишь небольшой частью числа Тем не менее с вычислительной точки зрения необходимы различные процедуры для проверки наличия в графе гамильтоновых циклов и построения таких циклов, так как оказывается [6], что проще найти гамильтонов цикл в графе, имеющем такой цикл, чем доказать, что не существует никакого гамильтонова цикла в графе, его не имеющем. Этот факт подсказывает, что более подходящим будет алгоритм, который начинает с верхней границы В для оптимального (минимального) числа перенастроек аппаратуры и последовательно дает и проверяет графы до тех пор, пока не будет найден граф не имеющий гамильтоновых циклов. Краткое описание такого алгоритма дается ниже.

Шаг 1. Найти верхнюю границу В для оптимального (минимального) числа необходимых перенастроек аппаратуры (см. приложение).

Шаг 2. Используя формулы (10.2) и (10.3), построить граф

Шаг 3. Определить, имеет ли граф гамильтонов цикл. Если то хранить этот цикл в виде вектора записав его на место предыдущего хранящегося цикла, и перейти к шагу 4 или шагу 5.

Шаг 4. перейти к шагу 2.

Шаг 5. Останов, является минимальным числом перенастроек аппаратуры, и последняя последовательность в является требуемой последовательностью производства продуктов.

Шаг 1 приведенного выше алгоритма требует дальнейших пояснений. Очевидно, что чем более точной будет начальная верхняя граница В, тем меньшее число итераций основного алгоритма придется сделать. Процедура получения хорошей оценки для верхней границы дана в приложении. Существование гамильтонова цикла в графе может быть установлено с использованием мультицепного алгоритма разд. 2.3.