An Immune Algorithm Based Robust Scheduling Methods

An Immune Algorithm Based Robust Scheduling Methods

Xingquan Zuo (Beijing University of Posts and Telecommunications, P.R. Chinal Harbin Engineering University, P.R. China)
DOI: 10.4018/978-1-60566-310-4.ch006
OnDemand PDF Download:


Inspired from the robust control principle, a robust scheduling method is proposed to solve uncertain scheduling problems. The uncertain scheduling problem is modeled by a set of workflow simulation models, and then a scheduling scheme (solution) is evaluated by the results of workflow simulations that are executed by using the workflow models in the set. A variable neighborhood immune algorithm (VNIA) is used to obtain an optimal robust scheduling scheme that has good performances for each model in the model set. The detailed steps of optimizing robust scheduling scheme by the VNIA are given. The antibody coding and decoding schemes are also designed to deal with resource conflicts during workflow simulation processes. Experimental results show that the proposed method can generate robust scheduling schemes that are insensitive for uncertain disturbances of scheduling environments.
Chapter Preview


Scheduling problems exist widely in actual production processes, and are very important for improving enterprise efficiency, reducing the labor of workers, and enhancing the competitive power of enterprises. In recent years, many scheduling methods are proposed, and most of them are used to solve definitive scheduling problems (Brucker, 1998; Hajri, 2000; Yang, 2001). But in actual production scheduling, there are a lot of uncertainties such as the uncertainty of process time and the failure of machines, which would lead the primary scheduling scheme become worst or even infeasible. Dynamic scheduling methods (Suresh, 1993) can solve such uncertain scheduling problems effectively, i.e., when dynamic events occur, a new scheduling scheme can be generated by rescheduling to deal with the changed scheduling environment.

Dynamic scheduling methods can generate feasible scheduling schemes, but for some trades such as civil aviation, frequent rescheduling is not a good idea and may cause some problems for airliners and passengers. When an accidental event occurs, we hope that the event would not influence the whole scheduled flight. In this condition, a “robust” flight scheduling is welcome that would still maintain good performances when the scheduling environment changes.

Along with the increasing requirement of robust scheduling method, researches on robust scheduling arouse much attention in recent years (Lin, 2004). Compared with dynamic scheduling, robust scheduling is a new research area, and there are still many problems needed to be solved, and the definition of robust scheduling has not been given explicitly until now. General speaking, robust scheduling can be considered as a suboptimum scheduling scheme that is not sensitive to noise environments, and it emphasizes on the stability of scheduling schemes. Byeon et al decomposed a scheduling problem into several sub-problems, and a heuristic algorithm was used to solve each sub-scheduling problem to obtain a robust scheduling scheme (Byeon, 1998). Jensen proposed a robust scheduling method based on robust optimization (Jensen, 2003). His method used a disconnected chart model to construct a scheduling neighborhood, all of the scheduling solutions in the neighborhood are used to evaluate scheduling schemes, and an optimal robust scheduling scheme is obtained by a genetic algorithm. Leon et al proposed a robust scheduling method based on genetic algorithm, and scheduling schemes was evaluated by the weighted sum of the expectation values and variances of the performance index “Makespan” (Leon, 1994).

Key Terms in this Chapter

Robust Scheduling: For an uncertain scheduling problem, the goal of robust scheduling is to generate a suboptimum scheduling scheme that is not sensitive to stochastic disturbances, i.e., robust scheduling emphasizes on the stability of scheduling schemes

Workflow: The automation of a business process, in whole or part, during which documents, information or tasks are passed from one participant to another for action, according to a set of procedural rules

Immune Algorithm: A kind of algorithms that is developed based on human’s immune principles.

Scheduling Scheme: Can be considered as a solution of a schedule problem.

Scheduling: Scheduling concerns the allocation of limited resources to tasks over time, and is a decision-making process with the goal of optimizing one or more objectives

Optimization Algorithms: is a kind of algorithms that are used for solving optimization problems.

Dynamic Scheduling: For an uncertain scheduling problem, when some dynamic events occur, a new scheduling scheme is generated to deal with the uncertain disturbances by identifying the stochastic disturbances and rescheduling

Job Shop Scheduling: Suppose m machines have to process n jobs, and each job consists of a set of operations that have to be processed in a special sequence

Complete Chapter List

Search this Book:
Editorial Advisory Board
Table of Contents
Lipo Wang
Hongwei Mo
Chapter 1
Fabio Freschi, Carlos A. Coello Coello, Maurizio Repetto
This chapter aims to review the state of the art in algorithms of multiobjective optimization with artificial immune systems (MOAIS). As it will be... Sample PDF
Multiobjective Optimization and Artificial Immune Systems: A Review
Chapter 2
Jun Chen, Mahdi Mahfouf
The primary objective of this chapter is to introduce Artificial Immune Systems (AIS) as a relatively new bio-inspired optimization technique and to... Sample PDF
Artificial Immune Systems as a Bio-Inspired Optimization Technique and Its Engineering Applications
Chapter 3
Licheng Jiao, Maoguo Gong, Wenping Ma
Many immue-inspired algorithms are based on the abstractions of one or several immunology theories, such as clonal selection, negative selection... Sample PDF
An Artificial Immune Dynamical System for Optimization
Chapter 4
Malgorzata Lucinska, Slawomir T. Wierzchon
Multi-agent systems (MAS), consist of a number of autonomous agents, which interact with one-another. To make such interactions successful, they... Sample PDF
An Immune Inspired Algorithm for Learning Strategies in a Pursuit-Evasion Game
Chapter 5
Luis Fernando Niño Vasquez, Fredy Fernando Muñoz Mopan, Camilo Eduardo Prieto Salazar, José Guillermo Guarnizo Marín
Artificial Immune Systems (AIS) have been widely used in different fields such as robotics, computer science, and multi-agent systems with high... Sample PDF
Applications of Artificial Immune Systems in Agents
Chapter 6
Xingquan Zuo
Inspired from the robust control principle, a robust scheduling method is proposed to solve uncertain scheduling problems. The uncertain scheduling... Sample PDF
An Immune Algorithm Based Robust Scheduling Methods
Chapter 7
Fabio Freschi, Maurizio Repetto
The increasing cost of energy and the introduction of micro-generation facilities and the changes in energy production systems require new... Sample PDF
Artificial Immune System in the Management of Complex Small Scale Cogeneration Systems
Chapter 8
Krzysztof Ciesielski, Mieczyslaw A. Klopotek, Slawomir T. Wierzchon
In this chapter the authors discuss an application of an immune-based algorithm for extraction and visualization of clusters structure in large... Sample PDF
Applying the Immunological Network Concept to Clustering Document Collections
Chapter 9
Xiangrong Zhang, Fang Liu
The problem of feature selection is fundamental in various tasks like classification, data mining, image processing, conceptual learning, and so on.... Sample PDF
Feature Selection Based on Clonal Selection Algorithm: Evaluation and Application
Chapter 10
Yong-Sheng Ding, Xiang-Feng Zhang, Li-Hong Ren
Future Internet should be capable of extensibility, survivability, mobility, and adaptability to the changes of different users and network... Sample PDF
Immune Based Bio-Network Architecture and its Simulation Platform for Future Internet
Chapter 11
Tao Gong
Static Web immune system is an important applicatiion of artificial immune system, and it is also a good platform to develop new immune computing... Sample PDF
A Static Web Immune System and Its Robustness Analysis
Chapter 12
Alexander O. Tarakanov
Based on mathematical models of immunocomputing, this chapter describes an approach to spatio-temporal forecast (STF) by intelligent signal... Sample PDF
Immunocomputing for Spatio-Temporal Forecast
Chapter 13
Fu Dongmei
In engineering application, the characteristics of the control system are entirely determined by the system controller once the controlled object... Sample PDF
Research of Immune Controllers
Chapter 14
Xiaojun Bi
In fact, image segmentation can be regarded as a constrained optimization problem, and a series of optimization strategies can be used to complete... Sample PDF
Immune Programming Applications in Image Segmentation
Chapter 15
Xin Wang, Wenjian Luo, Zhifang Li, Xufa Wang
A hardware immune system for the error detection of MC8051 IP core is designed in this chapter. The binary string to be detected by the hardware... Sample PDF
A Hardware Immune System for MC8051 IP Core
Chapter 16
Mark Burgin, Eugene Eberbach
There are different models of evolutionary computations: genetic algorithms, genetic programming, etc. This chapter presents mathematical... Sample PDF
On Foundations of Evolutionary Computation: An Evolutionary Automata Approach
Chapter 17
Terrence P. Fries
Path planning is an essential component in the control software for an autonomous mobile robot. Evolutionary strategies are employed to determine... Sample PDF
Evolutionary Path Planning for Robot Navigation Under Varying Terrain Conditions
Chapter 18
Konstantinos Konstantinidis, Georgios Ch. Sirakoulis, Ioannis Andreadis
The aim of this chapter is to provide the reader with a Content Based Image Retrieval (CBIR) system which incorporates AI through ant colony... Sample PDF
Ant Colony Optimization for Use in Content Based Image Retrieval
Chapter 19
Miroslav Bursa, Lenka Lhotska
The chapter concentrates on the use of swarm intelligence in data mining. It focuses on the problem of medical data clustering. Clustering is a... Sample PDF
Ant Colonies and Data Mining
Chapter 20
Bo-Suk Yang
This chapter describes a hybrid artificial life optimization algorithm (ALRT) based on emergent colonization to compute the solutions of global... Sample PDF
Artificial Life Optimization Algorithm and Applications
Chapter 21
Martin Macaš, Lenka Lhotská
A novel binary optimization technique is introduced called Social Impact Theory based Optimizer (SITO), which is based on social psychology model of... Sample PDF
Optimizing Society: The Social Impact Theory Based Optimizer
Chapter 22
James F. Peters, Shabnam Shahfar
The problem considered in this chapter is how to use the observed behavior of organisms as a basis for machine learning. The proposed approach for... Sample PDF
Ethology-Based Approximate Adaptive Learning: A Near Set Approach
Chapter 23
Dingju Zhu
Parallel computing is more and more important for science and engineering, but it is not used so widely as serial computing. People are used to... Sample PDF
Nature Inspired Parallel Computing
Chapter 24
Tang Mo, Wang Kejun, Zhang Jianmin, Zheng Liying
An understanding of the human brain’s local function has improved in recent years. But the cognition of human brain’s working process as a whole is... Sample PDF
Fuzzy Chaotic Neural Networks
About the Contributors