Mathematical Models of Flow Shop and Job Shop Scheduling Problems
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.
[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.
[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.
@article{"International Journal of Engineering, Mathematical and Physical Sciences:63081", author = "Miloš Šeda", title = "Mathematical Models of Flow Shop and Job Shop Scheduling Problems", 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.", volume = "1", number = "7", pages = "324-6", }
