Title

等速率平行機台在工件具有抵達時間和群組限制下求解最小化總延遲時間之排程問題

Translated Titles

Minimizing total tardiness on uniform parallel machine with job arrival and incompatible job families

Authors

朱良琪

Key Words

等速率平行機台 ; 群組限制 ; 抵達時間 ; 總延遲時間 ; uniform parallel machine ; job arrival ; incompatible job families ; total tardiness

PublicationName

中原大學工業與系統工程研究所學位論文

Volume or Term/Year and Month of Publication

2013年

Academic Degree Category

碩士

Advisor

蘇玲慧

Content Language

繁體中文

Chinese Abstract

本研究探討等速率平行機台(Uniform Parallel Machine)之排程問題,考慮n個工件f個群組在m台等速率平行機台上加工,工件具有抵達時間和群組限制,同一部機台上,如果正準備處理的工件與上一個工件所屬群族不同時,則必須加上整備時間。本研究以總延遲時間最小化為目標。 首先,利用啟發式演算法,將群組排入機台,以減少整備時間,再利用貪婪演算法找出重複時間(Overlap)較大的群組,移除工件並嘗試排入機台上每個位置,排入機台時需考慮工件之抵達時間,直到找到最小總延遲時間則停止。本研究在機台數為30台、群組數為50個、工件量為512個,當處理時間為[1,100]時,求解時間為248.02秒。

English Abstract

We consider the problem of scheduling n jobs with f families on m uniform parallel machines. Every job has arrival time and belongs to one family. We have to add setup time when machine is processing one job( this job’s family is different to last job ). Our objective is to minimize total tardiness. First, we use heuristic assign family into machine for reducing setup time then we find families with greater overlap and using greedy algorithm to remove jobs from machine . For those jobs witch are removed we try assign them into every position. When we are assigning jobs into machine , we must consider it’s arrival time. The average execution time of problem with 30 machines, 50 families, 512 jobs and processing time [1,00] can be solved in 286.79 seconds.

Topic Category 電機資訊學院 > 工業與系統工程研究所
工程學 > 工程學總論
Reference
  1. Alidaee, Bahram and Rosa, Duane (1997), 'Scheduling parallel machines to minimize total weighted and unweighted tardiness', Computers & Operations Research, 24 (8), 775-88.
    連結:
  2. Arkin, Esther M and Roundy, Robin O (1991), 'Weighted-tardiness scheduling on parallel machines with proportional weights', Operations Research, 39 (1), 64-81.
    連結:
  3. Azizoglu, Meral and Kirca, Omer (1998), 'Tardiness minimization on parallel machines', International Journal of Production Economics, 55 (2), 163-68.
    連結:
  4. Biskup, Dirk, Herrmann, Jan, and Gupta, Jatinder N. D. (2008), 'Scheduling identical parallel machines to minimize total tardiness', International Journal of Production Economics, 115 (1), 134-42.
    連結:
  5. Bozorgirad, Mir Abbas and Logendran, Rasaratnam (2012), 'Sequence-dependent group scheduling problem on unrelated-parallel machines', Expert Systems with Applications, 39 (10), 9021-30.
    連結:
  6. Dessouky, Maged M (1998), 'Scheduling identical jobs with unequal ready times on uniform parallel machines to minimize the maximum lateness', Computers & Industrial Engineering, 34 (4), 793-806.
    連結:
  7. Dogramaci, Ali and Surkis, Julius (1979), 'Evaluation of a heuristic for scheduling independent jobs on parallel identical processors', Management Science, 25 (12), 1208-16.
    連結:
  8. Drobouchevitch, Inna G. and Sidney, Jeffrey B. (2012), 'Minimization of earliness, tardiness and due date penalties on uniform parallel machines with identical jobs', Computers & Operations Research, 39 (9), 1919-26.
    連結:
  9. Du, Jianzhong and Leung, Joseph Y-T (1990), 'Minimizing total tardiness on one machine is NP-hard', Mathematics of operations research, 15 (3), 483-95.
    連結:
  10. Eom, D-H, et al. (2002), 'Scheduling jobs on parallel machines with sequence-dependent family set-up times', The International Journal of Advanced Manufacturing Technology, 19 (12), 926-32.
    連結:
  11. Framinan, Jose Manuel and Leisten, Rainer (2008), 'Total tardiness minimization in permutation flow shops: a simple approach based on a variable greedy algorithm', International Journal of Production Research, 46 (22), 6479-98
    連結:
  12. Guinet, Alain (1995), 'Scheduling independent jobs on uniform parallel machines to minimize tardiness criteria', Journal of Intelligent Manufacturing, 6 (2), 95-103.
    連結:
  13. Gupta, Jatinder ND and Maykut, Albert R (1973), 'Scheduling jobs on parallel processors with dynamic programming', Decision Sciences, 4 (4), 447-57.
    連結:
  14. Ho, Johnny C and Chang, Yih‐Long (1991), 'Heuristics for minimizing mean tardiness for m parallel machines', Naval Research Logistics (NRL), 38 (3), 367-81.
    連結:
  15. Lin, BMT and Jeng, AAK (2004), 'Parallel-machine batch scheduling to minimize the maximum lateness and the number of tardy jobs', International Journal of Production Economics, 91 (2), 121-34.
    連結:
  16. Jin, Feng, Song, Shiji, and Wu, Cheng (2009), 'A simulated annealing algorithm for single machine scheduling problems with family setups', Computers & Operations Research, 36 (7), 2133-38.
    連結:
  17. Kim, Dong-Won, et al. (2002), 'Unrelated parallel machine scheduling with setup times using simulated annealing', Robotics and Computer-Integrated Manufacturing, 18 (3), 223-31.
    連結:
  18. Koulamas, Christos (1997), 'Decomposition and hybrid simulated annealing heuristics for the parallel‐machine total tardiness problem', Naval Research Logistics (NRL), 44 (1), 109-25.
    連結:
  19. Lawler, Eugene L (1964), 'On scheduling problems with deferral costs', Management Science, 11 (2), 280-88.
    連結:
  20. Lee, Young Hoon and Pinedo, Michael (1997), 'Scheduling jobs on parallel machines with sequence-dependent setup times', European Journal of Operational Research, 100 (3), 464-74.
    連結:
  21. Lin, Yang-Kuei, Fowler, John W., and Pfund, Michele E. (2012), 'Multiple-objective heuristics for scheduling unrelated parallel machines', European Journal of Operational Research.
    連結:
  22. Lushchakova, Irina N. (2012), 'Preemptive scheduling of two uniform parallel machines to minimize total tardiness', European Journal of Operational Research, 219 (1), 27-33.
    連結:
  23. Pfund, Michele, Fowler, John W, and Gupta, Jatinder ND (2004), 'A survey of algorithms for single and multi-objective unrelated parallel-machine deterministic scheduling problems', Journal of the Chinese Institute of Industrial Engineers, 21 (3), 230-41.
    連結:
  24. Pfund, Michele, et al. (2008), 'Scheduling jobs on parallel machines with setup times and ready times', Computers & Industrial Engineering, 54 (4), 764-82.
    連結:
  25. Root, James G (1965), 'Scheduling with deadlines and loss functions on k parallel machines', Management Science, 11 (3), 460-75.
    連結:
  26. Sarıçiçek, İnci and Çelik, Cenk (2011), 'Two meta-heuristics for parallel machine scheduling with job splitting to minimize total tardiness', Applied Mathematical Modelling, 35 (8), 4117-26.
    連結:
  27. Shim, Sang-Oh and Kim, Yeong-Dae (2007), 'Scheduling on parallel identical machines to minimize total tardiness', European Journal of Operational Research, 177 (1), 135-46.
    連結:
  28. Suriyaarachchi, Rasika H. and Wirth, Andrew (2004), 'Earliness/tardiness scheduling with a common due date and family setups', Computers & Industrial Engineering, 47 (2-3), 275-88.
    連結:
  29. Uzsoy, R. (1995), 'Scheduling batch processing machines with incompatible job families', International Journal of Production Research, 33 (10), 2685-708.
    連結:
  30. Xi, Yue and Jang, Jaejin (2012), 'Scheduling jobs on identical parallel machines with unequal future ready time and sequence dependent setup: An experimental study', International Journal of Production Economics, 137 (1), 1-10.
    連結:
  31. Yalaoui, Farouk and Chu, Chengbin (2002), 'Parallel machine scheduling to minimize total tardiness', International Journal of Production Economics, 76 (3), 265-79.
    連結: