Title

受限於完成時間絕對差最小化之下平行機台完工時間最小化問題

Translated Titles

Minimizing makespan subject to minimize total absolute deviation of completion time in an identical parallel machine system

DOI

10.6840/CYCU.2010.00447

Authors

馮聖哲

Key Words

排程 ; 等效平行機台 ; TADC ; 最大完工時間 ; Scheduling ; Identical parallel machine ; TADC ; Makespan

PublicationName

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

Volume or Term/Year and Month of Publication

2010年

Academic Degree Category

碩士

Advisor

蘇玲慧

Content Language

繁體中文

Chinese Abstract

本研究針對等效平行機台(Identical Parallel Machine)在TADC (Total Absolute Deviation of Completion time)最小下使最大完工時間最小的雙目標問題加以探討。TADC為一種完成時間變異問題的衡量。本研究先提出最佳解求解方式來求得TADC在等效平行機台最小的最佳解,再利用BIP數學模式來最小化最大完工時間。透過模擬實驗分析此求解方式之求解效率,模擬中最大環境工作數量200個,機台30台,最佳解的平均求解時間約229.1秒。

English Abstract

This study addresses the identical parallel machine scheduling problem in which makespan are minimized subject to minimize TADC, denoted as P||TADC/ΣCmax . An optimal algorithm is first proposed to solve TADC on identical parallel machine, then a binary integer programming model is developed to minimize makespan. Computational Experiments are conducted and the computation results are reported.

Topic Category 電機資訊學院 > 工業與系統工程研究所
工程學 > 工程學總論
Reference
  1. Chen, W.Y., Sheen, G.J.,2007. Single-machine scheduling with multiple performance measures: Minimizing job-dependent earliness and tardiness subject to the number of tardy jobs. International Journal of Production Economics 109, 214-229
    連結:
  2. Framina, J.M., Leiste, R.,2006. A heuristic for scheduling a permutation flowshop with makespan objective subject to maximum tardiness.International Journal of Production Economics 99, 28-40
    連結:
  3. Ganesan, V.K., Sivakumar, A.I., 2006. Scheduling in static jobshops for minimizing mean flowtime subject to minimum total deviation of job completion times. International Journal of Production Economics 103, 633-647
    連結:
  4. Gowrishankar, K., Rajendran, C., Srinivasan, G.,2001. Flow shop scheduling algorithms for minimizing the completion time variance and the sum of squares of completion time deviations from a common due date. European Journal of Operational Research 132, 643-665
    連結:
  5. Ganesan, V.K., Sivakumar, A.I., Srinivasan, G.,2006. Hierarchical minimization of completion time variance and makespan in jobshops. Computers & Operations Research 33, 1345-1367
    連結:
  6. Gupta, J.N.D., Ho, J.C., Webster, S.,2000. Bicriteria optimisation of the makespan and mean flowtime on two identical parallel machines. Journal of the Operational Research Society 51, 1330-1339
    連結:
  7. Gupta, J.N.D., Ho, J.C., 2001. Minimizing makespan subject to minimum flowtime on two identical parallel machines. Computers & Operations Research 28, 705-717
    連結:
  8. Gupta, J.N.D., Neppalli, V.R., Werner, F.,2001. Minimizing total flow time in a two-machine flowshop problem with minimum makespan. International Journal of Production Economics 69, 323-338
    連結:
  9. Gupta, J.N.D., Ruiz-Torres, A.J.,2000. Minimizing makespan subject to minimum total flow-time on identical parallel machines. European Journal of Operational Research 125, 370-380
    連結:
  10. Ji, M., Cheng, T.C.E.,2010. Batch scheduling of simple linear deteriorating jobs on a single machine to minimize makespan. European Journal of Operational Research 202, 90-98
    連結:
  11. KANET, J.J., 1981. Minimizing variation of flow time in single machine systems. The Institute of Management Sciences 27, NO.12
    連結:
  12. Lin, C.H., Liao, C.J.,2004. Makespan minimization subject to flowtime optimality on identical parallel machines. Computers & Operations Research 31, 1655-1666
    連結:
  13. Li, Y., Li, G.., Sun, L., Xu, Z., 2009. Single machine scheduling of deteriorating jobs to minimize total absolute differences in completion times. International Journal of Production Economics 118, 424-429
    連結:
  14. Mosheiov, G., 2004. Simultaneous minimization of total completion time and total deviation of job completion times. European Journal of Operational Research 157, 296-306
    連結:
  15. Marangos, C.A., Govande, V., Srinivasan, G., Jr E.W.Z.,1998. Algorithms to minimize completion time variance in a two machine flowshop. Computers Industrial Engineering 35, 101-104
    連結:
  16. Mosheiov, G.,2005. Minimizing total completion time and total deviation of job completion times from a restrictive due-date. European Journal of Operational Research 165, 20-33
    連結:
  17. Nessah, R., Chu, C., 2010. A Lower Bound for Weighted Completion Time Variance. European Journal of Operational Research.
    連結:
  18. Ng, C.T., Cai, X., Cheng, T.C.E.,1996. A tight lower bound for the completion time variance problem. European Journal of Operational Research 92, 211-213
    連結:
  19. Oron, D., 2008. Single machine scheduling with simple linear deterioration to minimize total absolute deviation of completion times. Computers & Operations Research 35, 2071-2078
    連結:
  20. Srirangacharyulu, B., Srinivasan, G.,2010. Completion time variance minimizationin single machine and multi-machine systems. Computers & Operations Research 37, 62-71
    連結:
  21. Su, L.H.,2009. Minimizing earliness and tardiness subject to total completion time in an identical parallel machine system. Computers & Operations Research 36, 461-471
    連結:
  22. Tsiushuangt, C., Xiangtong, Q., Fengsheng, T.,1997. Single machine scheduling to minimize weighted earliness subject to maximum tardiness. Computers & Operations Research 24, 147-152
    連結:
  23. Viswanathkumar, G.., Srinivasan, G., 2003. A branch and bound algorithm to minimize completion time variance on a single processor. Computers & Operations Research 30, 1135-1150
    連結:
  24. Hardy, G. H., J. E. Littlewood and G. Polya, Inequalities, 1967. Cambridge University Press, London.