Volume 2 Issue 2 pp. 295-306 Spring, 2011


A new mathematical model for the job shop scheduling problem with uncertain processing times


M. A. Shafia, M. Pourseyed Aghaee and Amin Jamili


Job shop scheduling (JSS) problem has been one of the most interesting research issues in the literature during the recent years. JSS problem has been studied in different forms of deterministic, fuzzy, and stochastic at different depths. The idea of robust optimization (ROP), on the other hand, has earned a particular value to become a popular subject of the breakthrough for problem solving affairs amongst the researchers. Based on the emerged opportunity for illustrating a new area of search, a robust JSS problem is proposed as a challenge to this boundary of knowledge. The proposed method is capable of handling the perturbation which exists amongst the processing times. In fact, in many real world job scheduling problems, a small change in the processing times, not only causes a non-optimal solution, but also the infeasibility of the final solution may also occur. The proposed robust method could guarantee that, a small deviation of the processing times does not affect the feasibility. The implementation of the proposed method is illustrated using some numerical examples and the outcomes of the investigation are discussed.


DOI: 10.5267/j.ijiec.2010.03.005

Keywords: Job Shop Scheduling, Robust optimization, Simulated annealing, Heuristic, Mixed Integer Programming, Uncertainty, Interruption
References

Allet, S. (2003). Handling flexibility in a generalized job shop with a fuzzy approach. European Journal of Operational Research, 147, 312–333.

Baker, K. R. (1974). Introduction to sequencing and scheduling. New York: Wiley.

Ben-Tal, A., & Nemirovski, A. (2000). Robust solutions of linear programming problems contaminated with uncertain data. Mathematical Programming, 88, 411–424.

Bertsimas, D., & Sim., M. (2004). The price of robustness. Operations Research, 52, 35-53.

Bozejko, W., Pempera, J., & Smutnicki, C. (2009). Parallel Simulated Annealing for the Job Shop Scheduling Problem. In Proceedings of the 9th International Conference on Computational Science: Part I, 631 – 640.

Farhang Moghadam, B. & Seyedhosseini, S. M. (2010). A particle swarm approach to solve vehicle routing problem with uncertain demand: A drug distribution case study, International Journal of Industrial Engineering Computations, 1(1), 55-64.

Gharakhani, M., Taghipour, T. & Jalali Farahani, K. (2010). A robust multi-objective production planning, International Journal of Industrial Engineering Computations, 1(1), 73-78.

Garey, E.L., Johnson, D.S., & Sethi, R. (1976). The complexity of flowshop and job-shop scheduling. Mathematics of Operations Research, 1, 117–129.

Ginzburg, D.G., & Gonik, A. (2002). Optimal job-shop scheduling with random operations and cost objectives. International Journal of Production Economics, 76, 147–157.

Kacem, I., Hammadi, S., & Borne, P. (2002). Pareto-optimality Approach for Flexible Job-shop Scheduling Problems: Hybridization of Evolutionary Algorithms and Fuzzy Logic. Journal of Mathematics and Computers in Simulation, 60, 245-276.

Krishna, K., Ganeshan, K., & Janaki Ram D. (1995). Distributed Simulated Annealing Algorithms for Job Shop Scheduling, IEEE Transactions on systems. MAN. & Cybernetics, 25 (7), 1102-1109.

Ponnambalam, S. G., Jawahar, N., & Aravindan, P. (1999). A simulated annealing algorithm for job shop scheduling. Production Planning & Control, 10 (8), 767-777.

Shafia, M. A., Pourseyed Aghaee, M., Sadjadi, S. J., & Jamili, A. (2010). Robust Train Timetabling problem: Mathematical model and Branch and bound algorithm. Working paper

Shafia, M. A., Sadjadi, S. J., & Jamili, A. (2010). Robust Train Formation Planning. Proceedings of the IMechE Part F: Journal of Rail and rapid transit, 224(F2), 75-90.

Roghanian, E. & Foroughi, A. (2010). An empirical study of Iranian regional airports using robust data envelopment analysis, International Journal of Industrial Engineering Computations, 1(1), 65-72.

Soyster, A.L. (1973). Convex programming with set-inclusive constraints and applications to inexact linear programming. Operations Research, 21, 1154–1157.

Steinhofel, K., Albrecht, A., & Wong, C. K. (1999). Two simulated annealing-based heuristics for the job shop scheduling problem. European Journal of Operational Research, 118 (3) 524-548.

Suresh, R.K. , & Mohanasundaram, K.M. (2006). Pareto archived simulated annealing for job shop scheduling with multiple objectives. The International Journal of Advanced Manufacturing Technology, 29, 184-196.