## Group Shop Schedulingedited by Christian Blum, IRIDIA ## Contents## About 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 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:
## 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 |