Задача построения расписаний

ЗАДАЧА ПОСТРОЕНИЯ РАСПИСАНИЙ [c.139]

Формализуем задачу построения расписания. Момент поступления в систему заявки, приходящей ранее всех других, обозначим нулем. Символом Т обозначим время, отсчитываемое от нуля, в течение которого обслуживание всех поступивших в систему заявок будет завершено. Разобьем интервал (О, 7") на интервалы длиной Д (Д достаточно мало). Занумеруем интервалы Д числами к - , М. Если какая-то заявка на интервале (О,/V) поступает г раз (г > 1), каждое такое поступление будем считать отдельной заявкой. Моменты поступления заявок, отсчитанные от начала отсчета времени, обозначим через Уу, а время, необходимое на их обслуживание, через т.. Переменными т. обозначим моменты окончания обслуживания. Будем считать, что все с , и т. кратны Д. Индивидуальные функции потерь, возникающие в системе, если обслуживание заявки/ завершается не ранее момента т., обозначим (г.). [c.140]

Доказательство достаточности (4.9) и (4.10) дает возможность использовать алгоритм построения расписания, если исходные данные совместны. Воспользовавшись приведенным алгоритмом, задачу построения расписания для простейшего случая задания условий легко решить. [c.142]

Пример. 3. Решим нашу задачу построения расписания при другом критерии — минимуме времен переналадок. На рис. 3.28 показана диаграмма расписания. Видно, что применение данного критерия не дает того э екта, как в случае одного ГПМ. Это объясняется тем. [c.157]

В этой главе рассматриваются вопросы построения расписаний выполнения вычислительных работ в предположении, что расписание составляется после решения задачи выбора ЭВМ, с помощью алгоритмов, рассмотренных в гл. 3. [c.140]

Очевидно, что при этом расписание, минимизирующее потери, дает нулевое значение функционала, а все прочие — равное бесконечности. Если при конкретных значениях исходных данных минимум (4.8) имеет значение °°, будем говорить, что не обеспечивается возможность построения расписания, укладывающегося в предельные сроки. В этом случае будем говорить также, что исходные данные несовместимы. Таким образом, задача состоит в нахождении хотя бы одного расписания, укладывающегося в предельные сроки, либо в определении несовместимости данных оГ, Оу, 1. и т, исключающей возможность построения такого расписания. [c.142]

Примем следующие партии запуска - 11 й2 5 Дд = 11. Последовательность запуска заготовок примем такой же, как в предыдущем примере. Из диаграммы построенного расписания (рис. 3.26) видно, что изменение партий запусков изменило расписание так, что сумма времен простоев увеличилась до 86,5 мин. Попробуем вновь решить данную задачу с поиском оптимальной последовательности запусков деталей. [c.157]

Из многих экстремальных задач в области эксплуатации локомотивов, которые можно решать при помощи математического программирования, наиболее актуальна проблема машинного построения оптимального варианта графика движения поездов с наилучшими показателями использования локомотивов на участках обращения и зонах обслуживания большой протяженности и работы сменных локомотивных бригад по именным расписаниям. Алгоритм и программа для решения такой комбинаторной задачи составляются на основании тяговых расчетов, которые также выполняются на электронно-цифровых вычислительных машинах (ЭЦВМ). [c.272]

Алгоритм построения расписания одного станка с помощью метода ветвей и границ (МВГ) осуществляется следующим образом. Из вершины-источника 5 (рис. 3.21) начинается построение пути. Нижняя граница (НГ) Ь из условия задачи неопределима, так как не существует матрицы переналадок [Qф. При ветвлении к вершине присоединяется одна из аддитивных к ней вершин, которая удовлетворяет (3.27) и ограничениям (3.23), (3.24), (3.25) и (3.26). На первом пшге, как правило, определяют какое-либо текущее значение функционала, которое для последующих этапов служит НГ. После нахождения какого-либо пути 0 осуществляется возврат на графе ветвления в поисках пути с лучшей оценкой функционала, чем достигнутая, т.е. идет процесс оптимизации. При каждом включении какой-либо вершины е,у проверяется значение функционала и ограничения. Если на каком-ли шаге ветвления функционал больше, чем достигнутая нижняя граница (на предыдущем пути-расписании), или не выполняются ограничения (3.23)—(3.26), то осуществляют возврат и ветвление по другому пути. В итоге достигается оптимальное расписание работы одного ГПМ. [c.152]

Вопрос о введении единого счета времени для России, как государства с огромным протяжением по долготе, являлся особенно острым. С конца 70-х годов некоторые вновь построенные железные дороги (в основном частные) стали пользоваться местным временем, причем и здесь не было какого-либо единообразия за местное время принимали как время в одном из конечных пунктов данной железной дороги, так и время в ее срединной точке. Тем не менее в России дело не доходило до таких курьезов, как в США, где каждая железная дорога имела свое время, так что в 1883 г. образовалось 75 разновидностей местного времени, или как на Констанцском озере, где было 5 таких разновидностей по числу пяти государств, владевших его берегами (Швейцария, Австрия, Бавария, Баден и Вюртемберг). Устранение расхождений в счете времени в зависимости от долготы места для разных государств земного шара являлось одной из основных задач Вашингтонской конференции астрономов 1884 г. Однако в России, как и в других государствах, не было принято предложение конференции о введении единого вселенского счета времени, по которому вселенский день должен быть средним солнечным, начинаться везде с момента средней полуночи на Гринвичском меридиане (совпадающего с началом гражданских суток на нем) и считаться от О до 24 ч. Не было принято в России также поясное время , предложенное С. Флемингом в 1879 г. Для России задача являлась особенно трудной, и потому даже ученые астрономы считали в то время целесообразным воздержаться от радикальных мероприятий. Отмечая желательность объединения счета времени , второй директор Пулковской обсерватории О. В. Струве, представлявший Россию на Вашингтонской конференции, указывал, что в расписаниях поездов, составляемых для публики, следует удержать местное или то нормальное время, с которым сообразуется местная общественная жизнь [226]. Пулковское (петербургское) время было внедрено в железнодорожном, почтово-телеграфном и морском ведомствах, для гражданского же населения, в частности, для пассажиров железнодорожных поездов было сохранено местное время. [c.226]

Энциклопедия по машиностроению XXL

Оборудование, материаловедение, механика и ...