A modifi ed branch and bound algorithm for a vague flow-shop scheduling problem

Document Type : Research Paper


1 Department of Industrial Engineering, Mazandaran University of Science and Technology, Babol, Iran

2 2Department of Industrial Engineering, School of Engineering, Damghan University, Damghan, Iran

3 Department of Statistics, University of Campinas, R. Sergio Buarque de Holanda, 651, Campinas (CEP 13083-859), Brazil.


Uncertainty plays a significant role in modeling and optimization of real world systems. Among uncertain approaches, fuzziness describes impreciseness while for ambiguity another definition is required. Vagueness is a probabilistic model of uncertainty being helpful to include ambiguity into modeling different processes especially in industrial systems. In this paper, a vague set based on distance is used to model a flow-shop scheduling problem being an important problem in assembly production systems. The vagueness being used as octagon numbers are employed to represent vague processes for the manufacturing system. As a modeling effort, first a flow-shop scheduling problem is handled with vagueness. Then, for solving and analyzing the proposed vague flow-shop scheduling model, a modified Branch and Bound algorithm is proposed. As an implementation, an example is used to explain the performance and to analyze the sensitivity of the proposed vague approach. The validity of the proposed model and modified algorithm is demonstrated through a robust ranking technique. The outputs help the decision makers to counteract the vagueness and handle operational decisions in flow-shop scheduling problems within dynamic environments.


[1] G. Ambika, G. Uthra, Branch and Bound Technique in flow shop scheduling using fuzzy processing times, Annals of
Pure and Applied Mathematics, 8(2) (2014), 37{42.
[2] P. C. Bagga, N-job, 2-machine sequencing problem with stochastic service times, Operation Research, 18 (7) (1970),
[3] K. R. Baker, Introduction to sequencing and scheduling, John Wiley & Sons, 1974.
[4] J. Cheng, H. Kise, H. Matsumoto, A branch-and-bound algorithm with fuzzy inference for a permutation flowshop
scheduling problem, European Journal of Operational Research, 96(3) (1997), 578{590.
[5] P. Cowling, M. Johansson, Using real time information for effective dynamic scheduling, European journal of operational
research, 139(2) (2002), 230{244.
[6] V. Dhanalakshmi, F. C. Kennedy, Some Aggregation Operations on Octagonal Fuzzy Numbers and its Application
to Decision Making, 5(1) (2015), 145{160.
[7] W. L. Gau, D. J. Buehrer, Vague sets, IEEE transactions on systems, man, and cybernetics, 23(2) (1993), 610{614.
[8] V. A. Gonzalez-Lopez, R. Gholizadeh, A. M. Shirazi, Optimization of queuing theory based on vague environment,
International Journal of Fuzzy System Applications (IJFSA), 5(1) (2016), 1{26.
[9] D. Gupta, S. Sharma, S. Aggarwal, Flow shop scheduling on 2-machines with setup time and single transport facility
under fuzzy environment, Opsearch, 50(1) (2013), 14{24.
[10] T. P. Hong, T. N. Chuang, A new triangular fuzzy Johnson algorithm1, Computers & Industrial Engineering, 36(1)
(1999), 179{200.
[11] H. Ishibuchi, T. Murata, K. H. Lee, Formulation of fuzzy flowshop scheduling problems with fuzzy processing time,
Proceedings of the Fifth IEEE International Conference on Fuzzy systems, 1(2) (1996), 199{205.
[12] S. M. Johnson, Optimal two-and three-stage production schedules with setup times included, Naval research logistics
quarterly, 1(1) (1954), 61{68.
[13] C. Kao, C. C. Li, S. P. Chen, Parametric programming to the analysis of fuzzy queues, Fuzzy sets and systems,
107(1) (2006), 93{100.
[14] J. C. Ke, C. H. Lin, Fuzzy analysis of queueing systems with an unreliable server: A nonlinear programming
approach, Applied Mathematics and Computation, 175(1) (2006), 330{346.
[15] E. Khorram, V. Nozari, Multi-objective optimization with preemptive priority subject to fuzzy relation equation
constraints, Iranian Journal of Fuzzy Systems, 9(3) (2012), 27{45.
[16] B. L. Maccarthy, J. Liu, Addressing the gap in scheduling research: a review of optimization and heuristic methods
in production scheduling, The International Journal of Production Research, 31(1) (1993), 59{79.
[17] S. U. Malini, F. C. Kennedy, An approach for solving fuzzy transportation problem using octagonal fuzzy numbers,
Applied Mathematical Sciences, 7(54) (2013), 2661{2673.
[18] L. Martin, T. Roberto, Fuzzy scheduling with application to real time system, Fuzzy sets and Systems, 121(3)
(2001), 523{535.
[19] C. S. McCahon, E. S. Lee, Job sequencing with fuzzy processing times, Computers & Mathematics with Applications,
19(7) (1990), 31{41.
[20] C. S. McCahon, E. S. Lee Fuzzy job sequencing for a flow shop, European Journal of Operational Research, 62(3)
(1992), 294{301.
[21] A. Mehrabian, R. T.Moghaddam, K. K. Damaghani, Multi-objective routing and scheduling in flexible manufac-
turing systems under uncertainty, Iranian Journal of Fuzzy Systems, 14(2) (2017), 45{77.
[22] R. Nagarajan, A. Solairaju, Computing improved fuzzy optimal Hungarian assignment problems with fuzzy costs
under robust ranking techniques, International journal of computer application, 6(4) (2010), 263-276.
[23] P. Sanuja, S. Xueyan, A new approach to two machine flow shop problem with uncertain processing time, Optimization
and Engineering, 7(3) (2006), 329{343.
[24] C. S. Shukla, F. F. Chen, The state of the art in intelligent real-time FMS control: a comprehensive survey, Journal
of intelligent Manufacturing, 7(6) (1996), 441{455.
[25] T. P. Singh, P. Allawalia, Reformation of non fuzzy scheduling using the concept of fuzzy processing time under
blocking, International Conference on intelligence system & Networks, (2008), 322{324.
[26] T. P. Singh, P. Sunita, Allawalia Fuzzy ow shop problem on 2-machines with single transport facility-An heuristic
approach, Arya Bhatta Journal of Mathematics & Informatics, 1(1-2) (2009), 38{46.
[27] I. Temiz, S. Erol, Fuzzy branch-and-bound algorithm for flow shop scheduling, Journal of intelligent manufacturing,
15(4) (2004), 449{454.
[28] R. R. Yager, A procedure for ordering fuzzy subsets of the unit interval, Information sciences, 24(2) (1981), 143{161.