Minimizing makespan for flowshop scheduling problem with random and bounded processing times
List of Authors
  • Muberra Allahverdi

Keyword
  • Flowshop scheduling, uncertain processing times, makespan

Abstract
  • One of the assumptions in the scheduling literature is that job processing times are known fixed values. Even though this assumption is true for some manufacturing environments, on the other hand, the assumption does not hold for some other manufacturing environments. Therefore, job processing times should be considered as uncertain variables. In this paper, we address the four-machine flowshop scheduling problem with the objective of minimizing makespan where processing times are uncertain random variables. Since the problem is NP-hard, four heuristics are proposed. Extensive computational experiments are conducted to compare the performances of the proposed heuristics. Computational experiments indicate that one of the heuristics performs very well, and thus, it is recommended.

Reference
  • 1. Allahverdi, A., Aydilek, H. (2010a). Heuristics for two-machine flowshop scheduling problem to minimize makespan with bounded processing times. International Journal of Production Research, 48, 6367- 6385.

    2. Allahverdi, A., and Sotskov, Y.N. (2003). Two-machine flowshop minimum length scheduling problem with random and bounded processing times. International Transactions in Operational Research, 10, 65-76.

    3. Aydilek, H., and Allahverdi, A. (2010). Two-machine flowshop scheduling problem with bounded processing times to minimize total completion time. Computers and Mathematics with Applications, 59, 684-693.

    4. Gonzalez-Neira, E.M., Ferone, D., Hatami, S., Juan, A.A. (2017). A biased-randomized simheuristic for the distributed assembly permutation flowshop problem with stochastic processing times. Simulation Modelling Practice and Theory, 79, 23-36.

    5. Kouvelis, P., Yu, G. (1997). Robust Discrete Optimization and its Applications. Kluwer Academic Publisher.

    6. Lai, T.C., and Sotskov, Y.N. (1999). Sequencing with uncertain numerical data for makespan minimization”, Journal of the Operational Research Society, 50, 230-243.

    7. Lai, T.C., Sotskov, Y.N., Sotskova, N.Y., Werner, F. (1997). Optimal makespan scheduling with given bounds of processing times. Mathematical and Computer Modelling, 26, 67-86.

    8. Seidgar, H., Kiani, M., Abedi, M., et al. (2014). An efficient imperialist competitive algorithm for scheduling in the two-stage assembly flow shop problem”, International Journal of Production Research, 52, 1240-1256.

    9. Sotskov, Y.N., Allahverdi, A., Lai, T.C. (2004). Flowshop scheduling problem to minimize total completion time with random and bounded processing times”, Journal of Operational Research Society, 55, 277-286.

    10. Stefansson, H., Sigmarsdottir, S., Jensson, P., Shah, N. (2011). Discrete and continuous time representations and mathematical models for large productions scheduling problems: a case study from the pharmaceutical industry. European Journal of Operational Research, 215, 383-392.

    11. Tayanithi, P., Manivannan, S., Banks, J. (1992). A knowledge-based simulation architecture to analyze interruptions in a flexible manufacturing system. Journal of Manufacturing Systems, 11, 195-214.