PROJECTPUBLICATIONSALGORITHMSPROBLEMSprivate area
QAPMAX-SATSchedulingTimeTablingVehicle RoutingIndustrial

Group Shop Scheduling

Group Shop Scheduling

edited by Christian Blum, IRIDIA


Contents


About Group Shop Scheduling

In 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

M. Pinedo, 1995, Scheduling: Theory, Algorithms and Systems, Prentice Hall.

B. Giffler and G. L. Thompson. Algorithms for solving production scheduling problems. Operations Research, 8, pages 487-503, 1960.

D. Applegate and W. Cook. A Computational Study of the Job-Shop Scheduling Problem. ORSA Journal on Computing, 3, pages 149-156, 1991.

C. Blum. ACO Applied to Group Shop Scheduling: A Case Study on Intensification and Diversification. In M. Dorigo, G. Di Caro, and M. Sampels, editors, Proceedings of ANTS 2002 - Third International Workshop on Ant Algorithms, volume 2463 of Lecture Notes in Computer Science, pages 14-27. Springer Verlag, Berlin, Germany, 2002.

C. Blum. An Ant Colony Optimization Algorithm to tackle Shop Scheduling Problems. Technical Report TR/IRIDIA/2003-01, IRIDIA, Université Libre de Bruxelles, Belgium, 2003.

C. Blum and M. Sampels. Ant Colony Optimization for FOP Shop scheduling: A case study on different pheromone representations. In Proceedings of the 2002 Congress on Evolutionary Computation, CEC'02, volume 2, pages 1558-1563, 2002.

P. Brucker. Scheduling algorithms. Springer, Berlin, Germany, 1998.

P. Brucker, J. Hurink, B. Jurisch, and B. Wöstmann. A branch & bound algorithm for the open-shop problem. Discrete Applied Mathematics, 76, pages 43-59, 1997.

P. Brucker, B. Jurisch, and B. Sievers. A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49, pages 107-127, 1994.

J. Carlier and E. Pinson. An algorithm for solving the job-shop problem. Management Science, 35, 29, pages 164-176, 1989.

M. Dell'Amico and M. Trubian. Applying tabu search to the job-shop scheduling problem. Annals of Operations Research, 41, pages 231-252, 1993.

C.-F. Liaw. A tabu search algorithm for the open shop scheduling problem. Computers and Operations Research, 26, pages 109-126, 1999.

C.-F. Liaw. A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research, 124, pages 28-42, 2000.

H. R. Lourenço. Job-shop scheduling: Computational study of local search and large-step optimization methods. European Journal of Operational Research, 83, pages 347-364, 1995.

J. F. Muth and G. L. Thompson. Industrial Scheduling. Prentice Hall, Englewood Cliffs, NJ, USA, 1963.

E. Nowicki and C. Smutnicki. A fast taboo search algorithm for the job-shop problem. Management Science, 42, 2, pages 797-813, 1996.

M. Sampels, C. Blum, M. Mastrolilli, and O. Rossi-Doria. Metaheuristics for Group Shop Scheduling. In J.J. Merelo Guervós et al., editor, Proceedings of PPSN-VII, Seventh International Conference on Parallel Problem Solving from Nature, Lecture Notes in Computer Science, pages 631-640. Springer Verlag, Berlin, Germany, 2002. Also available as technical report TR/IRIDIA/2002-07, IRIDIA, Université Libre de Bruxelles.

T. Stützle. An Ant Approach to the Flow Shop Problem. In the Proceedings of the Fifth European Congress on Intelligent Techniques and Soft Computing, EUFIT'98, pages 1560-1564, 1998.

E. Taillard. Benchmarks for basic scheduling problems. European Journal of Operations Research, 64, pages 278-285, 1993.


Links

  • Results of the ACO algorithm developped in the network.
  • Website of the Whizzkids97 competition organized by the TU Eindhoven in 1997.

Network Coordinator: Marco Dorigo    e-mail: mdorigo@ulb.ac.be    Web site responsibles: Christian Blum and Max Manfrin