Skip to main content
Top

1994 | Book

Scheduling Theory. Multi-Stage Systems

Authors: V. S. Tanaev, Y. N. Sotskov, V. A. Strusevich

Publisher: Springer Netherlands

Book Series : Mathematics and Its Applications

insite
SEARCH

About this book

An increasing interest to scheduling theory can be attributed to the high level of automation of all branches of human activity. The quality of modern production essentially depends on the planning decisions taken at different stages of a production process. Moreover, while the quality of these decisions is improving, the time and flexibility requirements for decision-making are becoming more important. All this stimulates scheduling research. Started as an independent discipline in the early fifties, it now has become an important branch of operations research. In the eighties, the largest Russian publishing house for scientific literature Nauka Publishers, Moscow, issued two books by a group of Byelorussian mathematicians: Scheduling Theory. Single-Stage Systems by V. S. Tanaev, V. S. Gordon and Y. M. Shafransky (1984) and Scheduling Theory. Multi-Stage Systems by V. S. Tanaev, Y. N. Sotskov and V. A. Strusevich (1989). Originally published in Russian, these two books cover two different major problem areas of scheduling theory and can be considered as a two-volume monograph that provides a systematic and comprehensive exposition of the subject. The authors are grateful to Kluwer Academic Publishers for creating the opportunity to publish the English translations of these two books. We are indebted to M. Hazewinkel, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys and W. Szwarc for their supporting the idea of translating the books into English.

Table of Contents

Frontmatter
Introduction
Abstract
Many practical situations lead to the necessity of studying multi-stage systems, i.e., systems in which the processing of each job consists of several sequential stages, at each of which the job is processed on a certain machine or, in a more general case, on a certain set of machines. For example, manufacturing a workpiece usually includes several sequential operations, each of which is performed on some of the machine tools available at the workshop; a teacher gives lectures one after another for several specific groups of students; the process of preparing a book for publication involves stages such as writing, reviewing, editing, printing, etc.
V. S. Tanaev, Y. N. Sotskov, V. A. Strusevich
Chapter 1. Flow Shop
Abstract
The jobs of a set N = 1, 2,…, n are processed in a system consisting of M sequential machines. A job iN is available at time d i ≥ 0. The routes (machine processing orders) are identical for all jobs of set N and are determined by the sequence of machines 1, 2,…, M. The processing times t iL ≥ 0 of each job iN on each machine L, 1 ∈ LM, are given. Simultaneous processing of any job on several machines is not allowed. Moreover, each machine processes no more than one job at a time. Such a processing system is called a flow shop.
V. S. Tanaev, Y. N. Sotskov, V. A. Strusevich
Chapter 2. Job Shop
Abstract
The jobs of a set N = 1, 2,…, n are processed in a system consisting of M machines. A job iN enters the processing system at time d i ≥ 0. Processing this job includes r i stages. At a stage q, 1 ≤ qr i job i is processed on machine Li q M = 1, 2,…, M. Machines Liq 1 ≤qr i , need not be different. Machine passage routes L i = (Li1,Li2…, Liri) are given for each job iN, and may be different for different jobs. Each machine processes jobs one after another, and no more than one job at a time.
V. S. Tanaev, Y. N. Sotskov, V. A. Strusevich
Chapter 3. Open Shop
Abstract
The jobs of a set N = 1, 2,…, n are processed in a system consisting of M sequential machines. A job iN enters a system at time di > 0. For each job of set N, a route (a processing order) is not given in advance and may be different for different jobs. The processing times tiL ≥ 0 of each job iN on each machine L, 1 ≤ LM, are given. The notation tiL = 0 implies that job i is not processed on machine L. At any time, each job is processed on at most one machine, and each machine processes no more than one job. Such processing systems are called open shops.
V. S. Tanaev, Y. N. Sotskov, V. A. Strusevich
Chapter 4. Mixed Graph Problems
Abstract
All of the situations considered earlier can be interpreted in terms of resource-constrained project scheduling. To do so, we introduce the concept of an Operation as some process having a certain duration and consuming certain resources. Each two operations may be either dependent or independent in the sense that the calendar time of one of them either affects or does not affect that of another. Each machine may be considered as a non-accumulated indivisible resource which restricts the possibility of performing two or more operations of job processing simultaneously.
V. S. Tanaev, Y. N. Sotskov, V. A. Strusevich
Backmatter
Metadata
Title
Scheduling Theory. Multi-Stage Systems
Authors
V. S. Tanaev
Y. N. Sotskov
V. A. Strusevich
Copyright Year
1994
Publisher
Springer Netherlands
Electronic ISBN
978-94-011-1192-8
Print ISBN
978-94-010-4521-6
DOI
https://doi.org/10.1007/978-94-011-1192-8