Abstract
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.
TopBackground
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