MINIMIZING MEAN FLOW TIME FOR THE TWO-MACHINE SCHEDULING PROBLEM WITH A SINGLE SERVER
Abstract
The problem of scheduling jobs on two parallel machines to minimize the sum of completion times is considered. Each job requires a setup which is done by a single server. It is known that this problem is strongly NP-hard. Two mixed integer linear programming models and a simulated annealing algorithm are proposed. The performance of these algorithms is evaluated for instances with up to 250 jobs.
About the Authors
F. Werner
Университет Магдебурга, Германия
Germany
Germany
S. A. Kravchenko
Объединенный институт проблем информатики НАН Беларуси
Belarus
Belarus
K. Hasani
Исламский университет Азад, Иран
Islamic Republic of Iran
Islamic Republic of Iran
References
1. Hall, N. Parallel machine scheduling with a common server / N. Hall, C. Potts, C. Sriskandarajah // Discrete Applied Mathematics. – 2000. – Vol. 102. – P. 223–243.
2. Complexity results for parallel machine problems with a single server / P. Brucker [et al.] //Journal of Scheduling. – 2002. – Vol. 5. – P. 429–457.
3. Kravchenko, S.A. A heuristic algorithm for minimizing mean flow time with unit setups /S.A. Kravchenko, F. Werner // Information Processing Letters. – 2001. – Vol. 79. – P. 291–296.
4. Wang, G. An approximation algorithm for parallel machine scheduling with a common server / G. Wang, T.C.E. Cheng // J. of the Operational Research Society. – 2001. – Vol. 52. – P. 234–237.
5. Weng, M.X. Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective / M.X. Weng, J. Lu, H. Ren // International J. of Production Economics. – 2001. – Vol. 70. – P. 215–226.
6. Dunstall, S. Heuristic methods for the identical parallel machine flowtime problem with set-up times / S. Dunstall, A. Wirth // Computers & Operations Research. – 2005. – Vol. 32. – P. 2479–2491.
7. Azizoglu, M. Scheduling parallel machines to minimize weighted flowtime with family setup times / M. Azizoglu, S. Webster // International J. of Production Research. – 2003. – Vol. 41. – P. 1199–1215.
8. Guirchoun, S. Total completion time minimization in a computer system with a server and two parallel processors / S. Guirchoun, P. Martineau, J.-C. Billaut // Computers & Operations Research. – 2005. – Vol. 32. – P. 599–611.
9. Hasani, K. Two heuristics for minimizing the makespan for the two-machine scheduling problem with a single server / K. Hasani, S.A. Kravchenko, F. Werner. – Magdeburg, 2013. – 20 p. – (Preprint / Otto-von-Guericke-University Magdeburg, Faculty of Mathematics ; № 08/13).
Review
For citations:
Werner F., Kravchenko S.A., Hasani K. MINIMIZING MEAN FLOW TIME FOR THE TWO-MACHINE SCHEDULING PROBLEM WITH A SINGLE SERVER. Informatics. 2014;(1):15-24. (In Russ.)
Views: 714
Email this article 