Two-stage fuzzy-stochastic programming for parallel machine scheduling problem with machine deterioration and operator learning effect

Document Type : Research Paper


1 Iran University of Science and Technology

2 Iran university of science and technology


This paper deals with the determination of machine numbers and production schedules in manufacturing environments. In this line, a two-stage fuzzy stochastic programming model is discussed with fuzzy processing times where both deterioration and learning effects are evaluated simultaneously. The first stage focuses on the type and number of machines in order to minimize the total costs associated with the machine purchase. Based on the made decisions, the second stage aims to schedule orders, while the objective is to minimize total tardiness costs. A dependent-chance programming (DCP) approach is used for the defuzzification of the proposed model. As the resulted formulation is a NP-hard problem, a branch and bound (B&B) algorithm with effective lower bound is developed. Moreover, a genetic algorithm (GA) is proposed to solve problems of large-sizes. The computational results reveal the high efficiency of the proposed methods, in particular the GA, to solve problems of large sizes.


Main Subjects

Al-Khamis, T. & R. M’Hallah (2011) A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity. Computers & Operations Research, 38, 1747–1759.
Baptiste, P., J. Carlier, A. Kononov, M. Queyranne, S. Sevastyanov & M. Sviridenko (2012) Integer preemptive scheduling on parallel machines. Operations Research Letters, 40, 440–444.
Bozorgirad, M. A. & R. Logendran (2012) Sequence-dependent group scheduling problem on unrelated-parallel machines. Expert Systems with Applications, 39, 9021–9030.
Fanjul-Peyro, L., F. Perea & R. Ruiz (2017) MIP models and matheuristics for the unrelated parallel machine scheduling problem with additional resources. European Journal of Operational Research.
Gerstl, E. & G. Mosheiov (2012) Scheduling on parallel identical machines with job-rejection and position-dependent processing times. Information Processing Letters, 112, 743–747.
Gharehgozli, A. H., R. Tavakkoli-Moghaddam & N. Zaerpour (2009) A fuzzy-mixed-integer goal programming model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates. Robotics and Computer-Integrated Manufacturing, 25, 853–859.
Ji, M. & T. C. E. Cheng (2008) Parallel-machine scheduling with simple linear deterioration to minimize total completion time. European Journal of Operational Research 188, 342–347.
Joo, C. M. & B. S. Kim (2015) Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability. Computers & Industrial Engineering, 85, 102-109.
Kondakci, S., Ö. Kirca & M. Azizoǧlu (1994) An efficient algorithm for the single machine tardiness problem. International journal of production economics, 36, 213-219.
Lee, K. H. 2006. First course on fuzzy theory and applications. Springer.
Lee, W.-C., M.-C. Chuang & W.-C. Yeh (2012) Uniform parallel-machine scheduling to minimize makespan with position-based learning curves. Computers & Industrial Engineering, 63, 813–818.
Liao, L. W. & G. J. Sheen (2008) Parallel Machine Scheduling with Machine Availability and Eligibility Constraints. European Journal of Operation Research, 184, 458-467.
Liu, B. & Y.-K. Liu (2002) Expected value of fuzzy variable and fuzzy expected value models. IEEE Transactions on Fuzzy Systems, 10, 445–450.
Liu, M. (2013) Parallel-machine scheduling with past-sequence-dependent delivery times and learning effect. Applied Mathematical Modelling, 37, 9630–9633.
Liu, M., F. Zheng, S. Wang & Y. Xu (2013) Approximation algorithms for parallel machine scheduling with linear deterioration. Theoretical Computer Science, 497, 108–111.
Mazdeh, M. M., F. Zaerpour, A. Zareei & A. Hajinezhad (2010) Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs. Applied Mathematical Modelling, 34, 1498–1510.
Mosheiov, G. (2001) Scheduling problems with a learning effect. European Journal of Operation Research, 132, 687-693.
Peng, J. & B. Liu (2004) Parallel machine scheduling models with fuzzy processing times. Information Sciences, 166, 49–66.
Prot, D., O. Bellenguez-Morineau & C. Lahlou (2013) New complexity results for parallel identical machine scheduling problems with preemption, release dates and regular criteria. European Journal of Operational Research, 231, 282–287.
Rodriguez, F. J., M. Lozano, C. Blum & C. Garcı´a-Martı´nez (2013) An iterated greedy algorithm for the large-scale unrelated parallel machines scheduling problem. Computers & Operations Research, 40, 1829–1841.
Rostami, M., A. E. Pilerood & M. M. Mazdeh (2015) Multi-objective parallel machine scheduling problem with job deterioration and learning effect under fuzzy environment. Computers & Industrial Engineering, 85, 206-215.
Ruiz-Torres, A. J., G. Paletta & E. Pe´rez (2013) Parallel machine scheduling to minimize the makespan with sequence dependent deteriorating effects. Computers & Operations Research, 40, 2051–2061.
Sarıçiçek, I. & C. Çelik (2011) Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness. Applied Mathematical Modelling, 35, 4117–4126.
Shen, L., D. Wang & X.-Y. Wang (2013) Parallel-machine scheduling with non-simultaneous machine available time. Applied Mathematical Modelling, 37, 5227–5232.
Tian, W. & C. S. Yeo (2015) Minimizing total busy time in offline parallel scheduling with application to energy efficiency in cloud computing. Concurrency and Computation: Practice and Experience, 27, 2470-2488.
Toksari, M. D. & E. G¨uner (2009) Parallel machine earliness/tardiness scheduling problem under the effects of position based learning and linear/nonlinear deterioration. Computers & Operations Research, 36, 2394 -- 2417.
Unlu, Y. & S. J. Mason (2010) Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problems. Computers & Industrial Engineering, 58, 785–800.
Vallada, E. & R. Ruiz (2011) A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times. European Journal of Operational Research, 211, 612–622.
Yeh, W.-C., P.-J. Lai, W.-C. Lee & M.-C. Chuang (2013) Parallel-machine scheduling to minimize makespan  with fuzzy processing times and learning effects. Information Sciences.
Zadeh, L. A. (1965) Fuzzy sets. Inf. Control, 8, 338–353.
Zhang, M. & C. Luo (2013) Parallel-machine scheduling with deteriorating jobs, rejection and a fixed non-availability interval. Applied Mathematics and Computation, 224, 405–411.
Zhu, H. & J. Zhang (2009) A credibility-based fuzzy programming model for APP problem. In International conference on artificial intelligence and computational intelligence.