Production Planning and Scheduling Using Genetic Algorithms

Cheng, Runwei et al "Production Planning and Scheduling Using Genetic Algorithms" Computational Intelligence in Manufacturing Handbook Edited by Jun Wang et al Boca Raton: CRC Press LLC,2001 10 Production Planning and Scheduling Using Genetic Algorithms Runwei Cheng Ashikaga Institute of Technology Mitsuo Gen Ashikaga Institute of Technology 10.1 Introduction 10.2 Resource-Constrained Project Scheduling Problem 10.3 Parallel Machine Scheduling Problem 10.4 Job-Shop Scheduling Problem 10.5 Multistage Process Planning 10.6 Part Loading Scheduling Problem 10.1 Introduction Production scheduling problems concern the allocation of limited resources over time to perform tasks to satisfy certain criteria. Resources can be of a very different nature, for example, manpower, money, machines, tools, materials, energy, and so on. Tasks can have a variety of interpretations from machining parts in manufacturing systems up to processing information in computer systems. A task is usually characterized by some factors, such as ready time, due date, relative urgency weight, processing time, resource consumption, and so on. Moreover, a structure of a set of tasks, reflecting precedence constraints among them, can be defined in different ways. In addition, different criteria that measure the quality of the performance of a schedule can be taken into account. Many scheduling problems from manufacturing industries are characterized as combinatorial optimi-zation problems subject to highly complex constraints, which are very difficult to solve by conventional optimization techniques. This has led to the recent interest in using genetic algorithms to address the problem. In the following sections, we explain how to solve them with genetic algorithms, including resource-constrained project scheduling, parallel machine scheduling, job-shop scheduling, multistage process planning, and part loading scheduling problem. 10.2 Resource-Constrained Project Scheduling Problem The problem of scheduling activities under resource and precedence restrictions with the objective of minimizing the project duration is referred to as a resource constrained project scheduling problem in literature [Baker, 1974]. The basic type of the problem can be stated as follows: A project consists of a number of interrelated activities. Each activity is characterized by a known duration and given resource requirements. Resources are available in limited quantities but renewable from period to period. There is no substitution between resources and activities cannot be interrupted. A solution is to determine the start times of activities with respect to the precedence and resource constraints so as to optimize the objective. ©2001 CRC Press LLC The problem can be stated mathematically as follows: min tn Equation (10.1) s.t. tj 2 ti $di, ;j [ Si Equation (10.2) ^ r #b , k 5 1, 2,…,m Equation (10.3) ti [ Ati ti $0, i 5 1, 2,…,n Equation (10.4) where ti is the starting time of activity i, di the duration (processing time) of activity i, Si the set of successors of activity i, rik the amount of resource k required by activity i, bk the total availability of resource k, At the set of activities in process at time ti, and m the number of different resource types. Activities 1 and n are dummy activities that mark the beginning and end of the project. The objective is to minimize total project duration. Constraint 10.2 ensures that none of the procedence constraints are violated. Constraint 10.3 ensures that the amount of resource k used by all activities does not exceed its limited quantity in any period. The earliest attempts were made to find an exact optimal solution to the problem by using standard solution techniques of mathematical programming. Because the resource-constrained project scheduling problem is NP-hard, for large projects, the size of the problem may render optimal methods computa-tionally impracticable. In such cases, the problem is most amenable to heuristic problem solving, using fairly simple scheduling rules capable of producing reasonably good suboptimal schedules [Alvarez-Valdés and Tamarit, 1989]. Most heuristic methods known so far can be viewed as priority dispatching rules that assign activity priorities in making sequencing decisions for resolution of resource conflicts according to either temporally related heuristic rules or resource-related heuristic rules. In essentials, the problem consists of the following two basic issues: (i) to determine the processing order of activities without violating the precedence constraints and (ii) subsequently to determine the start time for each activity without violating the resource constraint. How to determine the order of activities is critical to the problem, because if the order of activities is determined, a schedule then can be easily constructed with some determining procedures according to the order. Cheng and Gen [1998] have proposed a hybrid genetic algorithm to the resource-constrained project scheduling problem. The basic idea of the approach is to (i) use genetic algorithms to evolve an appro-priate processing order of activities and (ii) use a fit-in-best procedure to calculate the start times of activities. Their study focuses on how to handle the precedence constraint existing in the problem. A new encoding method is proposed, which is essentially capable of representing all feasible permutations of activities for a given instance. 10.2.1 Priority-Based Encoding The key issue of the problem is to find an appropriate processing order of activities. This is a permutation problem in nature. Due to the existence of precedence constraints among activities, an arbitrary permu-tation may yield an infeasible processing order. Making an encoding that can treat the precedence constraint efficiently is a critical step and conditions all subsequent steps. A priority-based encoding method is proposed by Cheng and Gen to handle this difficulty, which is based on the concepts of a directed acyclic graph (DAG) model. A sample project can be represented with a directed acyclic graph. A directed acyclic graph G 5 (V, A) consists of a set of nodes V representing activities and a set of directed edges A representing the precedence constraints among activities. The terms node and activity will be used interchangeably in the following sections. For a given directed graph, a topological sort is a linear ordering of all its nodes such that for any ©2001 CRC Press LLC directed edge (u, v) [ A, node u appears before node v in the ordering. In other words, a topological sort corresponds to a feasible ordering of activities, that is, a feasible solution. Cheng and Gen suggest a new encoding method, priority-based encoding, which is capable of representing all possible topological sort for a given instance. Recall that a gene contains two kinds of information: locus, the position of the gene located within the structure of a chromosome, and allele, the value the gene takes. Here, the position is used to denote an activity ID and the value is used to denote the priority associated with the activity,as shown in Figure 10.1. The value of a gene is an integer exclusively within [1, n]. The larger the integer, the higher the priority. A one-pass procedure is used to generate a topological sort from a chromosome: to determine activities from left to right.When making a decision for a position, several activities may compete for the position and the one with the highest priority wins the position. The encoding does not explicitly represent a topological sort for a given DAG. It just contains some message for resolution of conflicts. A topological sort can be uniquely determined according to the encoding. Any changes in priorities usually result in a different topological sort. Therefore, this encoding is essentially capable of representing all possible topological sort for a given DAG. Let us see how to generate a topological sort from the encoding. Consider the example given in Figure 10.2. An array A[·] is used to store the generated topological sort. At the beginning, A[1] 5 1. Three activities, 2, 3, and 4, compete for A[2]. Their priorities as defined in above encoding are 7, 1, and 6, respectively. Activity 2 wins the position because it has the highest priority. After fixing A[2] 5 2, the candidates for the next position, A[3], are activities 3, 4, and 5. Activity 4 wins for the position and fixs A[3] = 4. Repeat these two steps: (i) construct the set of candidates for current position and (ii) select the highest-priority activity, until we obtain a topological sort, as shown in Figure 10.3 The tricky part, of course, is how to find a set of eligible nodes. The following definitions and theorems give us a better understanding about how to make such a set and how the procedure works. A partial topological sort is the one under development, which just contains the first t (t , | V |) nodes with fixed orders. Let PSt ,V be the set of nodes corresponding to a given partial topological sort, where 1 2 3 4 5 6 7 3 7 1 6 4 5 2 FIGURE 10.1 Priority-based encoding. 2 5 1 3 6 7 4 FIGURE 10.2 Network representation of a project. 1 2 4 5 3 6 7 FIGURE 10.3 The topological sort of the DAG shown in Figure 10.2. ©2001 CRC Press LLC 2 5 1 3 6 8 4 7 FIGURE 10.4 Partial topological sort, cut, and eligible nodes. the subscript t denotes the cardinal number of the set, that is, |PSt| 5 t. Let C(PSt, V 2 PSt ) 5 {(i, j) | i [ PSt, j [ V 2 PSt} be the cut of the directed graph with respect to the given partial topological sort. Then we have the following lemma: LEMMA 1 (eligible node) For a given partial topological sort with nodes PSt, a node j [ V 2 PSt is eligible if and only if we can have a set S(j) 5{(i, j) | (i, j)[ A} of edges incident to j such that S(j) # C(PSt, V2 PSt). PROOF. For a given node j [ V 2 PSt, if there is an edge (x, j) incident to j, the node x is a parent node of j. If all such edges belong to the cut C(PSt, V 2 PSt), it means that all the parent nodes of j belong to the set PSt, that is, they are the sorted node, therefore, the node j is eligible. Assume that there is an eligible node j and not all the edges incident to j belong to the cut. That is, |C(PSt, V 2 PSt) < S(j)|.|C(PSt, V 2 PSt)|. Then at least one of its parent node belongs to set V 2 PSt, that is, at least one of its parent node is not the sorted node. This is a contradiction to the definition of eligible node. j Theoretically, we can check whether a node is eligible with the lemma, but it is usually not easy for programming to check if a set is a subset of others. The following theorem provides a criterion to determine an eligible node. THEOREM 1 (criterion of eligible node) For an eligible node j [ V 2 PS , let S (j) be a proper subset of cut C(PSt, V 2 PSt) containing all edges incident to j, we have St(j) 5 dIN( j) . PROOF. For an eligible node, we have, according to Lemma 1, S(j) > S(j) 5 S(j) and S(j) < S(j) 5 S(j). Because S( j) 5 dIN( j , we prove the theorem. j Now we can identify an eligible node simply by checking whether the number of edges incident to it in the cut equals its indegree. This criterion is easy for programming. Let us consider the example given in Figure 10.4. The partial topological sort is PS3 5 {1, 2, 3} and the cut contains the directed edges C(PS3, V 2 PS3) 5 {(1, 4), (2, 5), (2, 6), (3, 6), (3, 7)}. Node 6 is an eligible one because its indegree dIN(6) 5 2 and the two edges incident to node 6 belong to the cut. Node 5 is a free node because its indegree is 2 and only one edge incident to it belongs to the cut. Its other parent node is 4, which is an eligible one but not a sorted one. 10.2.1.1 Procedure of Topological Sort The basic idea of the topological sort procedure is, at each step as the procedure progresses, to (i) identify the set of eligible nodes with Theorem 1, (ii) remove the one with the highest priority from the set, and (iii) fix the removed node in the partial topological sort. Let t be the iteration index of the procedure. Let V be the set of all node. Let Qi be the set of all direct successors of activities i. Let PS[·] be the array for storing topological sort. Let CUT[i] be the number of edges incident to node i in cut. Let St be the set of eligible nodes at step t. The procedure for generating a topological sort from a chromosome is given as below: procedure: topological sort step 1: (initialization) t ¬ 1 (iteration index) PS[t] ¬ 1 (initial topological sort) S ¬ Q (initial priority queue) CUT[i] ¬ 1, ;i [ Q1 (initial number of edges in the cut) ©2001 CRC Press LLC ... - tailieumienphi.vn