Solving parallel machine scheduling problem with release dates using genetic algorithm

  • Authors

    • Yasothei Suppiah
    • Ajitha Angusamy
    • Goh Wei Wei
    • Noradzilah bt Ismail
    2018-05-22
    https://doi.org/10.14419/ijet.v7i2.29.13136
  • Scheduling, Parallel machine, Genetic algorithm, Dispatching rule

  • Abstract

    This research deals with a scheduling problem for parallel machines environment to minimize total weighted tardiness with the consideration of sequence dependent setup times and release dates. There are two research questions that need to be addressed: 1) How to allocate jobs on machines ?  2) How to sequence jobs on each machine? Therefore, this research aims to find an efficient solution method that answers the research questions with the goal of minimizing the total weighted tardiness with the presence of sequence dependent setup times. Due to the complexity of the problem at hand, the authors have developed genetic algorithm to find a solution to this problem. Furthermore, various dispatching rules were used to enhance the performance of the genetic algorithm in terms of the total weighted tardiness value.

     

  • References

    1. [1]. Allahverdi A., Ng C.T., Cheng T.C.E., Kovalyov Mikhail Y. (2008). A survey of scheduling problems with setup times or costs. European Journal of Operational Research, 985-1032.

      [2]. Baker K.R. (1974). Introduction to sequencing and scheduling . Wiley New York.

      [3]. Behnamian J., Ghomi F., & Zandieh M. (2009). A multi-phase covering Pareto-optimal front method to multi-objective scheduling in a realistic hybrid flowshop using a hybrid metaheuristic. International Journal of Production Research, 48, 4949–4976.

      [4]. Chang O.K & Hyun J.S. (2003). Scheduling jobs on parallel machines: a restricted tabu search approach. International Journal of Advanced Manufacturing Technology 22, 278-287.

      [5]. Chen T., Rajendran C. and Wu C.W. (2013). Advanced dispatching rules for large-scale manufacturing. International Journal of Advanced Manufacturing Technology, 1-3.

      [6]. Conner G. (2009). 10 questions. Manufacturing Engineering Magazine.

      [7]. Demiral T., Özkır V., Demirel N. C. and Taşdelen B. (2011). A Genetic Algorithm Approach for Minimizing Total Tardiness in Parallel Machine Scheduling Problems. Proceedings of the World Congress on Engineering, Vol II WCE. London.

      [8]. Eom D.H., Shin H.J., Kwun I.H, Shim J.K & Kim S.S. (2002). Scheduling jobs on parallel machines with sequence-dependent family set-up times. The International Journal of Advanced Manufacturing Technology 19, 926-932.

      [9]. Graves S.C. (1981). A review of Production Scheduling. Operations Research, 646-675.

      [10]. Holland J.R. (1975). Adaptation in Natural and Artificial Systems. Ann Arbor: University of Michigan Press.

      [11]. Huegler P.A. and Vasko F.J. (1997). A performance comparison of heuristics for the total weighted tardiness problem. Computers and Industrial Engineering, 32(4), 753-767.

      [12]. Jin F., Song S. and Wu C. (2009). A simulated annealing algorithm for single machine scheduling problems with family setups. Computers and Operations Research,36 , 2133-2138.

      [13]. Joo C.M. & Kim B.S. (2015). Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability. Computers & Industrial Engineering, 85, 102-109.

      [14]. Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G. (1982). Recent developments in deterministic sequencing and scheduling: A survey. In Deterministic and Stochastic Scheduling (pp. 35-74).

      [15]. Lee Y.H., Bhaskaran K. and Pinedo M. (1997). A heurisitic to minimize the total weighted tardiness with sequence-dependent setups. IIE Transactions, 29(1), 45-52.

      [16]. Lenstra J.K., Rinnooy Kan A.H.G. and Brucker P. (1977). Complexity of machine scheduling problems. Annals of Discrete Mathematics, 343-362.

      [17]. Lin Y.K. and Lin C.W. (2013). Dispatching rules for unrelated parallel machine scheduling with release dates. International Journal of Advanced Manufacturing Technology, 67, 269-279.

      [18]. Lin Y.K., Pfund M.E. and Fowler J.W. (2011). Heuristics for minimizing regular performance measures in unrelated parallel machine scheduling problem. Computers & Operations Research, 38 (6), 901–916.

      [19]. Malve S. & Uzsoy R. (2007). A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families. Computers & Operations Research, 34, 3016-3028.

      [20]. Morton T.E. and Pentico D.W. (1993). Heuristic Scheduling Systems: With Applications to Production Systems and Project Management. John Wiley and Sons.

      [21]. Pfund M., Fowler J.W., Gadkari A. and Chen Y. (2008). Scheduling jobs on parallel machines with setup times and ready times. Computers and Industrial Engineering, 764-782.

      [22]. Pinedo M. (1995). Scheduling: Theory, Algorithms and Systems. Prentice Hall.

      [23]. Pinedo M. (2002). Scheduling Theory, Algorithms and Systems, (2nd ed). Prentice Hall.

      [24]. Schaller J.E. (2014). Minimizing total tardiness for scheduling identical parallel machines with family setups. Computers & Industrial Engineering,72, 274-281.

      [25]. Shih W.L., Zne J.L., Kuo C.Y., Chung C.L. (2011). Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates. Computers & Operations Research 38, 809–815.

      [26]. Vepsalainen A.P.J and Morton T.E. (1987). Priority rules for job shops with weighted tardiness cost., 33(8), 1035-1047. Management Science 33(8), 1035-1047.

      [27]. Volgenant A. and Teerhuis E. (1999). Improved heuristics for the n-job single-machine weighted tardiness problem. Computers and Operations Research, 26(1), 35-44.

      [28]. Zhou H., Cheung W. and Leung L.C. (2009). Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. European Journal of Operational Research, 194 (3) , 637-649.

      [29]. Zhu X., Wilhelm W.E. (2006). Scheduling and lot sizing with sequence-dependent setup: a literature review. IIE Transactions, 987-1007.

  • Downloads

  • How to Cite

    Suppiah, Y., Angusamy, A., Wei Wei, G., & bt Ismail, N. (2018). Solving parallel machine scheduling problem with release dates using genetic algorithm. International Journal of Engineering & Technology, 7(2.29), 91-96. https://doi.org/10.14419/ijet.v7i2.29.13136

    Received date: 2018-05-21

    Accepted date: 2018-05-21

    Published date: 2018-05-22