Сохранность книги — хорошая

COMPUTER AND JOB-SHOP SCHEDULING THEORY
Ed. by E. G. COFFMAN, Jr.

Coauthors:
J. L. BRUNO, E. G. COFFMAN, Jr., R. L. GRAHAM, W. H. KOHLER, R. SETHI, K. STEIGLITZ, J. D. ULLMAN

John Wiley & Sons
1976

Пер. англ. В. М. Амочкина

Формат 84x108 1/32. Бумага типографская №1. Печать высокая

Предлагаемая книга посвящена задачам теории расписаний — важной области прикладной математики, имеющей многочисленные и разнообразные применения. Она содержит достаточно полное и одновременно компактное изложение результатов решения основных задач, таких, как минимизация конечного и среднего времени завершения работ одним и несколькими исполнителями с учётом различных условий. Ранее советский читатель мог ознакомиться с теорией расписаний по книге В. С. Танаева и В. В. Шкурбы «Введение в теорию расписаний» и по переводу на русский язык книги Р. В. Конвея, В. Л. Максвелла и Л. В. Миллера «Теория расписаний», вышедшими в свет в издательстве «Наука» в 1975 г.

Материал данной книги изложен в терминах расписаний для однопроцессорных и многопроцессорных вычислительных систем. Для расписаний использованы, в основном, детерминированные математические модели (с заранее известными параметрами), в которых предусмотрены наборы как взаимосвязанных, так и независимых заданий или работ и соответствующие совокупности ресурсов для их исполнения. Эти модели, несмотря на их простоту, настолько содержательны, что охватывают очень широкий круг практически важных задач упорядочения, выходящих за рамки начальных формулировок. Результаты решений даны в виде эффективных оптимальных алгоритмов, эвристических алгоритмов с оценкой их эффективности и соответствующими границами, а также эффективных алгоритмов перебора и приближённых алгоритмов для построения разнообразных расписаний. Специфические вопросы применения ЭВМ не рассматриваются.

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

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

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

Вследствие того, что главы книги написаны разными авторами, имеются некоторые различия в стиле изложения, способах представления результатов и обозначениях. Эти обстоятельства, а также всё ещё недостаточно устоявшаяся терминология в теории расписаний вызвали определённые трудности при переводе. Предлагаемая книга выдержала проверку временем и является одной из наиболее цитируемых в своей области. Несмотря на то, что после её выхода в свет получен ряд новых результатов (см., например, […], материал книги представляет большой интерес для читателей в нашей стране, поскольку многие приведённые в ней результаты имеют основополагающий характер в теории расписаний и, кроме того, большинство изложенных результатов не публиковалось на русском языке.

ОТ РЕДАКТОРА ПЕРЕВОДА
Б. А. Головкин
декабрь 1982 г.

От редактора перевода	5
Предисловие	7

Г л а в а 1. Введение в детерминированную теорию расписаний.
*Э. Г. Коффман*	9

1.1. Цели и предпосылки	9
1.2. Основная модель	13
1.3. Предшествующие результаты для случая одного процессора	22
1.4. Точные и приближённые результаты для задач минимизации длины
расписаний и среднего времени прохождения	27
1.5. Другие задачи упорядочения	49
1.6. Обозначения	63

Г л а в а 2. Алгоритмы построения расписаний минимальной
длины. Р. Сети	65

2.1. Введение	65
2.2. Системы заданий с древовидной структурой	68
2.3. Двухпроцессорные расписания для систем заданий с произвольным
частичным упорядочением	75
2.4. Реализация алгоритмов без прерываний	86
2.5. Прерывания при независимых заданиях	92
2.6. Обобщения алгоритмов без прерываний	96
2.7. Преимущества прерываний	104
2.8. Процессоры с разным быстродействием	108
2.9. Конвейерная задача	112
Библиографическая справка	116

Г л а в а 3. Критерий среднего взвешенного времени
прохождения. Дж. Л. Бруно	118

3.1. Введение	118
3.2. Модель	119
3.3. Предварительные замечания	120
3.4. Алгоритмы	126
3.5. Модель со случайными величинами	132
3.6. Ранговая функция	136
3.7. Оптимальные расписания	138
3.8. Алгоритмы для моделей, содержащих случайные величины	142
3.9. Составление расписаний для многопроцессорных систем	146
3.10. Сведение	146
3.11. Многопроцессорные алгоритмы	149
3.12. Специальные случаи	156

Г л а в а 4. Сложность задач упорядочения. Дж. Ульман	158

4.1. Введение	158
4.2. Задачи и полиномиальная сводимость	159
4.3. Модель вычислительной машины	163
4.4. Недетерминированные вычисления	165
4.5. NP-полная задача	168
4.6. NP-полнота задачи составления расписаний	174
4.7. NP-полнота задачи минимизации среднего взвешенного
времени прохождения	177
4.8. NP-полнота задачи составления расписаний при единичных
временах выполнения	179
4.9. Составление расписаний для двух процессоров и времён
выполнения, равных 1 и 2	184
4.10. Составление расписаний с ограничениями на ресурсы	186
Библиографическая справка	188

Г л а в а 5. Оценки характеристик алгоритмов составления
расписаний. Р. Грэхем	190

5.1. Аномалии многопроцессорных расписаний	190
5.2. Оценки для независимых заданий без дополнительных ресурсов	202
5.3. Замечания о составлении расписаний методом критического пути	212
5.4. Составление расписаний при наличии многих ресурсов	217
5.5. Задача об упаковке в контейнеры	229
5.6. Оценки для некоторых других задач	246

Г л а в а 6. Перечислительные и итеративные алгоритмы.
*В. Коглер, К. Штиглиц*	249

6.1. Введение	249
6.2. Алгоритмы ветвей и границ для задач о перестановках	251
6.3. Приближённые алгоритмы	288
6.4. Алгоритмы решения конвейерной задачи	293
6.5. Взаимосвязь между методом ветвей и границ и
динамическим программированием	307
6.6. Заключительные замечания	315

Литература	318
Литература, добавленная при переводе	326

Предметный указатель	333

Книги на ту же тему

Введение в теорию расписаний, Танаев В. С., Шкурба В. В., 1975
Преобразования и перестановки, Калужнин Л. А., Сущанский В. И., 1979
Элементы динамического программирования, Вентцель Е. С., 1964
Эффективное функционирование управляющих мультипроцессорных систем, Вайрадян А. С, Коровин А. В., Удалов В. Н., 1984
Параллельные вычислительные системы, Головкин Б. А., 1980

elapsed time 0.022 sec

/Наука и Техника/Математика

ОГЛАВЛЕНИЕ

Книги на ту же тему