Mathematical Models of Flow Shop and Job Shop Scheduling Problems

Authors: Miloš Šeda

Abstract:

In this paper, mathematical models for permutation flow shop scheduling and job shop scheduling problems are proposed. The first problem is based on a mixed integer programming model. As the problem is NP-complete, this model can only be used for smaller instances where an optimal solution can be computed. For large instances, another model is proposed which is suitable for solving the problem by stochastic heuristic methods. For the job shop scheduling problem, a mathematical model and its main representation schemes are presented.

Keywords: Flow shop, job shop, mixed integer model, representation scheme.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1082307

References:

[1] E. Balas and A. Vazacopoulos, "Guided Local Search with Shifting Bottleneck for Job Shop Scheduling," Management Science, vol. 44, pp. 262-275, 1998
[2] J.E. Beasley, "OR-Library," Report, The Management School Imperial College, London, http://mscmga.ms.ic.ac.uk/pub/flowshop1.txt.
[3] J. Blazewicz, K.H. Ecker, G. Schmidt and J. Weglarz, Scheduling Computer and Manufacturing Processes. Berlin: Springer-Verlag, 1996.
[4] A. Brooke, D. Kendrick and A. Meeraus, GAMS Release 2.25. A User-s Guide. Massachussets: The Scientific Press, Boyd & Fraser Publishing Company, 1992.
[5] R. Cheng, M. Gen and Y. Tsujimura, "A Tutorial Survey of Job-Shop Scheduling Problems Using Genetic Algorithms - {I}. Representation," Computers & Industrial Engineering, vol. 30, pp. 983-997, 1996.
[6] Dubois and H. Prade, Theorie des possibilites. Applications a la representation des connaissances en informatique. Paris: MASSON, 1988.
[7] A. El-Bouri, N. Azizi and S. Zolfaghari, "A Comparative Study of a New Heuristic Based on Adaptive Memory Programming and Simulated Annealing: The Case of Job Shop Scheduling," European Journal of Operational Research, 2007, 17 pp., in press.
[8] D.E. Goldberg, Genetic Algorithms in Search, Optimization and Machine Learning. New York: Addison-Wesley, 1989.
[9] K. Gowrishankar, C. Rajendran and G. Srinivasan, "Flow Shop Scheduling Algorithms for Minimizing the Completion Time Variance and the Sum of Squares of Completion Time Deviations from a Common Due Date," European Journal of Operational Research, vol. 132, pp. 643-665, 2001.
[10] G. Gutin and A.P. Punnen (eds.), The Traveling Salesman Problem and Its Variations. Dordrecht: Kluwer Academic Publishers, 2002.
[11] H. Ishibuchi, N. Yamamoto, T. Murata and H. Tanaka, "Genetic Algorithms and Neighborhood Search Algorithms for Fuzzy Flowshop Scheduling Problems," Fuzzy Sets and Systems, vol. 67, pp. 81-100, 1994.
[12] H. Ishibuchi, S. Misaki and H. Tanaka, "Modified Simulated Annealing Algorithms for Flow Shop Sequencing Problem," European Journal of Operational Research, vol. 81, pp. 388-398, 1995.
[13] A. Jain and S. Meeran, "Deterministic Job-Shop Scheduling: Past, Present and Future," European Journal of Operational Research, vol. 113, pp. 390-434, 1999.
[14] C. Koulamas, "A New Constructive Heuristic for the Flowshop Scheduling Problem" European Journal of Operational Research, vol. 105, pp. 66-71, 1998.
[15] Z. Michalewicz and D.B. Fogel, How to Solve It: Modern Heuristics. Berlin: Springer-Verlag, 2000.
[16] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Berlin: Springer-Verlag, 1996.
[17] T. Murata, H. Ishibuchi and H. Tanaka, "Genetic Algorithms for Flowshop Scheduling Problems," Computers & Industrial Engineering, vol. 30, No. 4, pp. 1061-1071, 1996.
[18] V. Novák, Fuzzy Sets and their Applications, Bristol: Adam Hilger, 1989.
[19] E. Nowicki and C. Smutnicki, "A Fast Taboo Search Algorithm for the Job Shop Problem," Management Science, vol. 42, pp. 797-813, 1996.
[20] J.C.-H. Pan, J.-S. Chen and C.-M. Chao, "Minimizing Tardiness in a Two-Machine Flow-Shop," Computers & Operations Research, vol. 29, pp. 869-885, 2002.
[21] C.R. Reeves, Modern Heuristic Techniques for Combinatorial Problems. Oxford: Blackwell Scientific Publications, 1993.
[22] M. ┼áeda, J. Dvoř├ík and P. Majer, "Scheduling with Fuzzy Processing Times in a Flow Shop," in Proc. of the 7th European Congress on Fuzzy and Intelligent Techniques & Soft Computing EUFIT '99, Aachen, 1999, 6 pp.
[23] U.A. Turki, C. Fedjki and A. Andijani, "Tabu Search for a Class of Single-Machine Scheduling Problems," Computers & Operations Research, vol. 28, pp. 1223-1230, 2001.
[24] R. Vaessens, E. Aarts and J. Lenstra, "Job Shop Scheduling by Local Search," INFORMS Journal on Computing, vol. 8, pp. 302-317, 1996.
[25] J.P. Watson, A. Howe and L. Whitley, "Deconstructing Nowicki and Smutnicki's i-TSAB Tabu Search Algorithm for the Job-Shop Scheduling Problem," Computers & Operations Research, vol. 33, pp. 2623-2644, 2006.
[26] H. Wenqi and Y. Aihua, "An Improved Shifting Bottleneck Procedure for the Job Shop Scheduling Problem," Computers & Operations Research, vol. 31, pp. 2093-2110, 2004.
[27] T. Yamada and C.R. Reeves, "Permutation Flowshop Scheduling by Genetic Local Search," in Proc. of the International Conference Genetic Algorithms in Engineering Systems: Innovations and Applications GALESIA 97, Glasgow, 1997, pp. 232-238.
[28] S.H. Zegordi, K. Itoh and T. Enkawa, "Minimizing Makespan for Flow Shop Sequencing by Combining Simulated Annealing with Sequencing Knowledge," European Journal of Operational Research, vol. 85, pp. 515-531, 1995.