Презентация на тему Урок-практикум. Задачи теории расписаний (Информатика, 11 класс)

целевой функцией в транспортной задаче?
3. Что является контролируемыми факторами

в транспортной задаче?
4. Что такое удельные расходы?

перевозок от поставщиков к потребителям с помощью некоторых транспортных

средств.
Составленный план должен обеспечивать выполнение таких условий, как:
• полное удовлетворение спроса потребителей;
• вывоз всей продукции от поставщика;
• минимизация транспортных затрат.
Суммарные затраты на перевозки являются целевой функцией.

расписаний рассматриваются комплексы работ, связанных общим объектом или общим

исполнителем, направленные на достижение определенной цели. Модели теории расписаний позволяют найти наиболее дешевый или наиболее быстрый порядок выполнения работ.
К задачам выбора самого дешевого порядка выполнения работ относится
Задача о шлюзе.
Шлюз может пропускать в порядке очереди только по одному судну. Если создается очередь, то необходимо определить такой порядок прохождения судов через шлюз, при котором будет минимален ущерб от простоя.

быстрого порядка выполнения работ относится
Задача о двух станках.
Предстоит

изготовить N деталей, каждая из которых сначала обрабатывается на первом станке, затем — на втором. Необходимо выбрать такой порядок обработки, чтобы полное время выполнения работы было минимальным.
Порядок обработки, минимизирующий время Т, называется оптимальным.

Например, первый — токарный, второй — шлифовальный. Требуется изготовить

N деталей, каждая из которых сначала обрабатывается на первом станке, затем — на втором. Считается, что время обработки i-й детали на j-м станке известно и равно tij.
Необходимо выбрать такой порядок обработки, т.е. расписание работы станков, чтобы полное время Т, затраченное на изготовление всех деталей, было минимальным.

поставленной задачи был предложен С. М. Джонсоном в 1950-х

годах. Идея его состоит в том, чтобы расставить очередность обработки деталей так, чтобы минимизировать время простоя 2-го станка. Опишем суть алгоритма.
Задана матрица времени обработки для каждой детали на каждом станке. В первом столбце матрицы — номера деталей.

деталей надо выбрать минимальное значение. Если минимальное значение принимают

несколько величин, то можно выбрать любую из них.
Если это время относится к обработке детали на первом станке, то поставить деталь (строку в матрице, соответствующую этой детали) в начало списка обработки, в противном случае — в конец списка.
Затем надо исключить деталь из рассмотрения и повторить все действия с оставшимися деталями.
После m шагов будет получен оптимальный порядок обработки деталей.

сегодняшнего урока: ____.
На уроке по этой теме я

узнал: ____.
На уроке я научился: ____.
Лучше всего у меня получалось: ____.
Основные трудности при изучении темы: ____.
Оцените ваши чувства и ощущения во время изучения темы: восторг, норма, недовольство.
Чтобы я изменил на уроке, чтобы улучшить свои результаты: ____.

Подведение итогов, рефлексия