|
 | |
 | |
 |
Group Shop Schedulingedited by Christian Blum, IRIDIA ContentsAbout Group Shop SchedulingIn the industrial world, many problems that need to be solved, or optimized, are scheduling problems [Pinedo ...]. Imagine a factory where a number of products need to be produced. Each of these products can be called a job that is consisting of a number of operations that need to be executed to create the final product itself. Each of these operations are to be executed on a specific machine in the factory, and machines are shared among the products. The goal is mostly to finish all the products in an amount of time as small as possible. Therefore an optimal schedule for processing the operations of different products on the machines has to be found.This kind of scheduling problem is commonly called a Shop Scheduling problem. Group Shop Scheduling (GSS) is a very general formulation of Shop Scheduling problems. In fact, it comprises many of the accademically well-studied Shop Scheduling problem such as Job Shop Scheduling (JSS), Open Shop Shop Schedulin (OSS), and Flow Shop Scheduling (FSS). As all these problems are NP-hard, we can derive the NP-hardness of the GSS. The GSS problem was mentioned for the first time in the context of a competition organized by the TU Eindhoven in 1997 (see http://www.win.tue.nl/whizzkids/1997). More formally, in a Shop Scheduling problem, we have given a finite set of operations O that is partitioned into subsets M = {M1,...,Mm} (machines) and into subsets J = {J1,...,Jn} (jobs). Mk is the set of operations which have to be processed on machine k, and Ji is the set of operations which belong to job i. Furthermore, all operations o in O have a processing time denoted by p(o). In the Job Shop Scheduling, we have given a total order on the operations of each job, which determines the order in which they have to be processed. A solution to the problem consists in finding a total order on the operations of each machine. In contrast, in the Open Shop Scheduling, we have given no order at all. This means, that a solution to the problem consists in finding total orders on the operations of each job, and a total order on the operations of each machine. In the Group Shop Scheduling, we have given a refinement of the partition J to a partition into groups G = {G1,...,Gg}. On the groups of each job we have a given a total order. So, for example, the operations of the first group of a job have to be processed before the operations of the second group. A solution to the problem consists in finding a total order on the operations of each group, and a total order on the operations of each machine. A simple instance for the GSS on 10 operations partitioned into 3 jobs, 6 groups and 4 machines (processing times are omitted in this example) is shown below. The instance is depicted in the disjunctive graph representation [Giffler and Thompson, 1960]. The instance specification is as follows: O = {0,...,9}, J = {J1 = {0,1,2}, J2 = {3,...,6}, J3 = {7,8,9}}, M = {M1 = {0,4,7}, M2 = {1,3,8}, M3 = {2,6}, M4 = {5,9}}. The 3 jobs are partitioned into the following groups: G = {G1 = {0,1}, G2 = {2}, G3 = {3}, G4 = {4,5,6}, G5 = {7}, G6 = {8,9}}. The nodes of the graph correspond to the operations, and we have directed arcs symbolizing the given partial order on the operations. Furthermore, there are undirected arcs between every pair of operations being in the same group or having to be processed on the same machine. In order to obtain a solution, the undirected arcs have to be directed without creating any cycles. (b) A solution to the problem (the arcs undirected in (a) are directed such that the resulting graph does not contain any cycles).
Readings
Links
|
 |
|
 |
|
|
Network Coordinator: Marco Dorigo e-mail: mdorigo@ulb.ac.be Web site responsibles: Christian Blum and Max Manfrin |