Time-Dependent Scheduling

By: Stanis?aw Gawiejnowicz

Write A Review

Hardcover | 26 September 2008

At a Glance

Hardcover
400 Pages

Dimensions(cm)
23.39 x 15.6 x 2.24

Hardcover

$273.07

or 4 interest-free payments of $68.27 with

Aims to ship in 7 to 10 business days

hebookpresentedtothereaderisdevotedtotime-dependentscheduling. TScheduling problems, in general, consist in the allocation of resources over time in order to perform a set of jobs. Any allocation that meets all requirements concerning the jobs and resources is called a feasible schedule. The quality of a schedule is measured by a criterion function. The aim of scheduling is to ?nd, among all feasible schedules, a schedule that optimizes the criterion function. A solution to an arbitrary scheduling problem consists in giving a polynomial-time algorithm generating either an optimal schedule or a schedule that is close to the optimal one, if the given scheduling problem has been proved to be computationally intractable. The scheduling problems are subject of interest of the scheduling theory, originated in mid-?fties of the twentieth century. The theory has been developing dynamically and new research areas constantly come into existence. The subject of this book, ti- dependent scheduling, is one of such areas. In time-dependent scheduling, the processing time of a job is variable and depends on the starting time of the job. This crucial assumption allows us to apply the scheduling theory to a broader spectrum of problems. For example, in the framework of the time-dependent scheduling theory we may consider the problems of repayment of multiple loans, ?re ?ghting and maintenance assignments. In this book, we will discuss algorithms and complexity issues concerning various time-dependent scheduling problems.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Computing & I.T.Computer Science Artificial Intelligence Mathematics Optimisation Linear Programming Mathematical Theory of Computation Computer Programming & Software Development Algorithms & Data Structures Business & Management Operational Research

Fundamentals
Preliminaries	p. 3
Mathematical notation	p. 3
Sets and vectors	p. 3
Sequences	p. 4
Functions	p. 5
Logical notation	p. 5
Other notation	p. 6
Basic definitions and results	p. 6
Bibliographic notes	p. 13
Problems and algorithms	p. 15
Decision and optimization problems	p. 15
Encoding schemata	p. 16
Undecidable and decidable problems	p. 17
Basic concepts related to algorithms	p. 17
Time and space complexity of algorithms	p. 18
Polynomial-time algorithms	p. 18
Exponential-time algorithms	p. 19
Pseudopolynomial-time algorithms	p. 19
Exact algorithms	p. 19
Enumerative algorithms	p. 20
Branch-and-bound algorithms	p. 20
Dynamic programming algorithms	p. 20
Approximation algorithms	p. 21
Approximation schemata	p. 22
Offline algorithms vs. online algorithms	p. 22
Heuristic algorithms	p. 23
Greedy algorithms	p. 23
Local search algorithms	p. 24
Metaheuristics	p. 24
The presentation of algorithms	p. 24
Bibliographic notes	p. 26
NP-complete problems	p. 27
Basic definitions and results	p. 27
Examples of NP-complete problems	p. 31
Bibliographic notes	p. 33
Basics of the scheduling theory	p. 35
Parameters of the scheduling problem	p. 35
Parameters of the set of jobs	p. 35
Parameters of the set of machines	p. 36
Parameters of the set of resources	p. 38
The notion of schedule	p. 39
The presentation of schedules	p. 40
Parameters characterizing a job in schedule	p. 40
Types of schedules	p. 41
The criteria of schedule optimality	p. 43
Notation of scheduling problems	p. 45
Bibliographic notes	p. 46
Basics of time-dependent scheduling	p. 47
The scheduling theory vs. time-dependent scheduling	p. 47
Scheduling multiprocessor tasks	p. 48
Scheduling on machines with variable processing speeds	p. 48
Scheduling jobs with variable processing times	p. 48
Formulation of time-dependent scheduling problems	p. 49
Terminology and notation	p. 51
Applications of time-dependent scheduling	p. 53
Scheduling problems with deteriorating job processing times	p. 53
Scheduling problems with shortening job processing times	p. 54
Other examples of time-dependent scheduling problems	p. 54
Scheduling problems with time-dependent parameters	p. 55
Bibliographic notes	p. 56
Complexity
Single-machine time-dependent scheduling	p. 59
Minimizing the maximum completion time	p. 59
Proportional deterioration	p. 59
Proportional-linear deterioration	p. 66
Linear deterioration	p. 67
Simple non-linear deterioration	p. 75
General non-linear deterioration	p. 78
Proportional-linear shortening	p. 89
Linear shortening	p. 90
Non-linear shortening	p. 100
Minimizing the total completion time	p. 103
Proportional deterioration	p. 103
Proportional-linear deterioration	p. 106
Linear deterioration	p. 106
Simple non-linear deterioration	p. 111
General non-linear deterioration	p. 112
Linear shortening	p. 114
Minimizing the maximum lateness	p. 118
Proportional deterioration	p. 118
Proportional-linear deterioration	p. 118
Linear deterioration	p. 119
Simple non-linear deterioration	p. 121
General non-linear deterioration	p. 122
Linear shortening	p. 122
Other criteria	p. 123
Proportional deterioration	p. 123
Proportional-linear deterioration	p. 126
Linear deterioration	p. 128
Simple non-linear deterioration	p. 135
General non-linear deterioration	p. 137
Proportional-linear shortening	p. 142
Linear shortening	p. 142
Summary and tables	p. 147
Parallel-machine time-dependent scheduling	p. 155
Minimizing the maximum completion time	p. 155
Proportional deterioration	p. 155
Linear deterioration	p. 158
Linear shortening	p. 159
Minimizing the total completion time	p. 160
Proportional deterioration	p. 160
Linear deterioration	p. 162
Simple non-linear deterioration	p. 163
Linear shortening	p. 163
Other criteria	p. 164
Proportional deterioration	p. 164
Linear deterioration	p. 165
Summary and tables	p. 167
Dedicated-machine time-dependent scheduling	p. 171
Minimizing the maximum completion time	p. 171
Proportional deterioration	p. 171
Proportional-linear deterioration	p. 177
Linear deterioration	p. 180
Simple non-linear deterioration	p. 184
Proportional-linear shortening	p. 186
Minimizing the total completion time	p. 186
Proportional deterioration	p. 186
Linear deterioration	p. 189
Proportional-linear shortening	p. 191
Minimizing the maximum lateness	p. 192
Proportional deterioration	p. 192
Proportional-linear deterioration	p. 193
Linear deterioration	p. 193
Proportional-linear shortening	p. 194
Other criteria	p. 194
Proportional deterioration	p. 194
Proportional-linear deterioration	p. 194
Proportional-linear shortening	p. 195
Summary and tables	p. 196
Algorithms
Approximation and heuristic algorithms	p. 203
Minimizing the maximum completion time	p. 203
Proportional deterioration	p. 203
Linear deterioration	p. 209
General non-linear deterioration	p. 213
Linear shortening	p. 221
General non-linear shortening	p. 224
Minimizing the total completion time	p. 226
Proportional deterioration	p. 226
Linear deterioration	p. 231
Linear shortening	p. 233
Minimizing the maximum lateness	p. 234
Linear deterioration	p. 234
General non-linear deterioration	p. 235
Other criteria	p. 236
Proportional deterioration	p. 236
Linear deterioration	p. 237
General non-linear deterioration	p. 239
Linear shortening	p. 240
Concluding remarks	p. 240
Greedy algorithms based on signatures	p. 245
Preliminaries	p. 245
Problem formulation	p. 245
Definition of signatures	p. 246
Basic properties of signatures	p. 247
A greedy algorithm	p. 251
Signatures of regular sequences	p. 254
Sequences of consecutive natural numbers	p. 254
Arithmetic sequences	p. 263
Geometric sequences	p. 264
Arbitrary sequences	p. 265
Concluding remarks	p. 265
Local search algorithms	p. 267
Preliminaries	p. 267
Basic definitions	p. 267
General concepts in local search	p. 268
Applicability of local search algorithms	p. 269
Selected types of local search algorithms	p. 269
Iterative improvement algorithms	p. 269
Steepest descent search algorithms	p. 270
Simulated annealing algorithms	p. 271
Genetic and evolutionary algorithms	p. 272
Local search time-dependent scheduling algorithms	p. 273
Steepest descent search algorithms	p. 273
Iterative improvement algorithms	p. 276
Experimental evaluation of algorithms H[subscript 54] and H[subscript 58]	p. 277
Simulated annealing algorithms	p. 278
Evolutionary algorithms	p. 279
Concluding remarks	p. 282
Advanced Topics
Matrix methods in time-dependent scheduling	p. 285
Preliminaries	p. 285
Problem formulation	p. 285
Notation	p. 286
Auxiliary result	p. 286
A matrix approach	p. 286
The matrix form of single-machine schedules	p. 287
The matrix form of parallel-machine schedules	p. 288
The l[subscript p] norm criterion	p. 289
Preliminaries	p. 289
Results	p. 290
Equivalent problems	p. 292
The initial problem	p. 292
The transformed problem	p. 294
Detailed results	p. 296
Concluding remarks and open problems	p. 298
Scheduling dependent deteriorating jobs	p. 299
Preliminaries	p. 299
Chain precedence constraints	p. 304
Tree and forest precedence constraints	p. 307
Series-parallel constraints	p. 312
General precedence constraints	p. 315
Concluding remarks and open problems	p. 318
Time-dependent scheduling with two criteria	p. 321
Preliminaries	p. 321
Problems formulation	p. 321
Preliminary results	p. 322
Pareto optimality	p. 324
Scalar optimality	p. 328
Computational experiments	p. 335
Concluding remarks and open problems	p. 337
Afterword	p. 339
References	p. 341
List of Figures	p. 357
List of Tables	p. 359
Author Index	p. 363
Subject Index	p. 367
Symbol Index	p. 375
Table of Contents provided by Ingram. All Rights Reserved.

Time-Dependent Scheduling

At a Glance

Hardcover

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Computer Science

The Nvidia Way

Jensen Huang and the Making of a Tech Giant

Python Crash Course

3rd Edition - A Hands-On, Project-Based Introduction to Programming

Network Models in Finance

Expanding the Tools for Portfolio and Risk Management

Windows 11 For Seniors For Dummies, 2nd Edition

Python All-in-One For Dummies

3rd Edition

Digital Influence Warfare in the Age of Social Media

Praeger Security International

Co-Intelligence

Living and Working with AI

Information Governance Technologies

A Guide

Fuzzy Methods for Assessment and Decision Making

Exploring the Metaverse

Challenges and Applications

Robotics Goes MOOC

Interaction

Improving Decision Making Using Semantic Web Technologies

Multifidelity Modeling in Vibration Analysis

Machine Learning in Farm Animal Behavior using Python

Generative Artificial Intelligence and Fifth Industrial Revolution

Reasoning Web. Declarative Artificial Intelligence

Knowledge, Rules, Logic : 19th International Summer School 2023 Oslo, Norway, September 21-24, 2023, Tutorial Lectures

Advances in Automation VI

Proceedings of the International Russian Automation Conference, RusAutoCon2024, September 8-14, 2024, Sochi, Russia

Enterprise Fortress

The Ultimate Handbook for Enterprise Security Architecture

Image Analysis in Stroke Diagnosis and Interventions

4th International Workshop, SWITCH 2024, and 6th International Challenge, ISLES 2024, Held in Conjunction with MICCAI 2024, Marrakesh, Morocco, October 10, 2024, Proceedings

Intelligent Communication, Control and Devices

Proceedings of ICICCD 2024

Advances of Machine Learning for Knowledge Mining in Electronic Health Records

Equipment Intelligent Operation and Maintenance

Proceedings of the First International Conference on Equipment Intelligent Operation and Maintenance (ICEIOM 2023), Hefei, China, 21st - 23rd September, 2023 (Volume II)

Enterprise Fortress

The Ultimate Handbook for Enterprise Security Architecture

Artificial Intelligence

A Modern Approach, 4th Global Edition

This product is categorised by