衰退性工作的排程問題在最近二十年來逐漸受到了重視。在許多的現實情況中，某些類型的工作會因為開始處理時間的延宕，導致之後必須付出更多時間處理，這種類型的工作就稱作「衰退性工作」。因此在本研究中，將假設工作的處理時間不是一個定值，而是會隨著時間遞增的簡單線性函數。另一方面，透過將性質相似的工作群組化處理，可以提升生產的效能，這種現象在相關文獻中以「群組技術」稱之。然而，同時探討衰退性工作以及群組技術的相關研究卻不多。
在本研究中，在目標為最小化最後完工時間的前提下，考量了兩種衰退性工作的群組排程問題：第一種是以群組技術作為條件限制，探討衰退性工作的群組排程問題，並提出一多項式時間演算法解決之；第二種是在沒有群組技術的條件限制下，探討同樣的排程問題，並以一分支界限演算法解決之。

Deteriorating jobs scheduling has received great attention in the past two decades. In many realistic situations, a job processed later needs more time for processing than the same job when it is processed earlier; this phenomenon is known as deteriorating jobs. We consider the case of deteriorating jobs whose processing times are a simple linear increasing function of their starting time. On the other hand, the production efficiency can be increased by grouping jobs with similar processing requirements. This phenomenon is known as the group technology(GT) in the literature. However, there exist only a few result considering scheduling problems with deteriorating jobs and group technology simultaneously.
In this paper, we consider two group scheduling problems of minimizing the makespan with deteriorating jobs. One is a group scheduling problem with deteriorating jobs under GT assumption, and the other is a problem with the same model without GT assumption. We provide a polynomial-time algorithm and a branch-and-bound algorithm to solve the problems respectively.

[1] B. Alidaee, and N.K. Womer, "Scheduling with time dependent processing times: review and extensions", Journal of the Operational Research Society, Vol. 50, pp. 711-720 (1999)

[2] K.R. Baker, and D. Trietsch, Principles of Sequencing and Scheduling , John Wiley and Sons, pp. 301-303 (2009)

[3] K.R. Baker, and D. Trietsch, Principles of Sequencing and Scheduling , John Wiley and Sons , pp. 181-182 (2009)

[4] S. Browne, and U. Yechiali, "Scheduling deteriorating jobs on a single processor", Operations Research, Vol. 38, pp. 495-498 (1990)

[5] D. Chen, S. Li, and G. Tang, "Single machine scheduling with common due date assignment in a group technology environment", Mathematical Computation Modeling, Vol. 25, pp. 81-90 (1997)

[6] T.C.E. Cheng, Q. Ding, and B.M.T. Lin, "A concise survey of scheduling with time-dependent processing times", European Journal of Operation Research, Vol. 152 , pp. 1-13 (2004)

[7] T.C.E. Cheng, C.C. Wu, and W.C. Lee, "Some scheduling problems with deteriorating jobs and learning effects", Computers and Industrial Engineering, Vol. 54, pp. 972-982 (2008)

[8] C.C. Chiou, M.J. Yao, and J.T. Tsai, "A mutually beneficial coordination mechanism for a one-supplier multi-retailers supply chain", International Journal of Production Economics, Vol. 108, pp. 314-328 (2007)

[9] A.X. Guo, and J.B. Wang, "Single machine scheduling with deteriorating jobs under the group technology assumption", Internal Journal of Pure and Applied Mathematics, Vol. 18 (2), pp. 225-231 (2005)

[10] J.N.D. Gupta, and S.K.Gupta, "Single facility scheduling with nonlinear processing times", Computers and Industrial Engineering, Vol. 14, pp. 387-393 (1988)

[11] I. Ham, K. Hitomi, and T. Yoshida, "Group Technology: Applications to Production Management", Kluwer-Nijhoff, Boston (1985)

[12] L.Y. Kang, and C.T. Ng, "A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs", International Journal of Production Economics, Vol. 109, pp. 180-184 (2007)

[13] C. Koulamas, and G.J. Kyparisis, "Single-machine scheduling problems with past-sequence-dependent delivery times", International Journal of Production Economics, Vol. 126 , pp. 264-266 (2010)

[14] A.S. Kunnathur, and S.K. Gupta, "Minimizing the makespan the late start penalties added to processing times in a single facility scheduling problem", European Journal of Operational Research, Vol. 47, pp. 56-64 (1990)

[15] W.C. Lee, Y.H. Chung, and C.C. Wu, "Scheduling deteriorating jobs on a single machine with release times", Computers and Industrial Engineering, Vol. 54, pp. 441-452 (2008)

[16] W.C. Lee, and Z.S. Lu, "Group scheduling with deteriorating jobs to minimize the total weighted number of late jobs", Applied Mathematics and Computation, Vol. 218, pp. 8750-8757 (2012)

[17] W.C. Lee, C.C. Wu, C.C. Wen, and Y.H. Chung, "A two-machine flowshop makespan scheduling problem with deteriorating jobs", Computers and Industrial Engineering, Vol. 54, pp. 737-749 (2008)

[18] M. Liu, F.F. Zheng, C.B. Chu, and Y.F. Xu, "Single-machine scheduling with past-sequence-dependent delivery times and release times", Information Processing Letters, Vol. 112, pp. 835-838 (2012)

[19] G. Mosheiov, "Scheduling jobs under simple linear deterioration", Computers and Operations Research Journal, Vol. 21, pp. 653-659 (1994)

[20] C.T. Ng, and T.C.E. Cheng, "Group scheduling with controllable setup and processing times: minimizing total weighted completion time", Annals of Operations Research, Vol. 133, pp. 147-163 (2005)

[21]M.L. Pinedo, Scheduling Theory, Algorithms, and Systems, Springer, pp.84 (2008)

[22] J. Schaller, "Scheduling on a single machine with family setups to minimize total tardiness", International Journal of Production Economics, Vol. 105, pp. 329-344 (2007)

[23] T.G. Voutsinas, and P.P. Costas, "Scheduling jobs with values exponentially deteriorating over time", International Journal of Production Economics, Vol. 79, pp. 163 (2002)

[24] X.L. Wang, and T.C.E. Cheng, "Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan", European Journal of Operational Research, Vol. 178, pp. 57-70 (2007)

[25] J.B. Wang, W.J. Gao, L.Y. Wang, and D. Wang, "Single machine group scheduling with general linear deterioration to minimize the makespan", The International Journal of Advanced Manufacturing Technology, Vol. 43, pp. 146-150 (2009)

[26] J.B. Wang, L. Lin, and F. Shan, "Single-machine group scheduling problems with deteriorating jobs", The International Journal of Advanced Manufacturing Technology, doi:10.1007/s00170-007-1255-x (2007)

[27] J.B. Wang, C.T.D. Ng, T.C.E. Cheng, and L.L. Liu, "Minimizing total completion time in a two-machine flow shop with deteriorating jobs", Applied Mathematics and Computation, Vol. 180, pp. 185-193 (2006)

[28] S. Webster, and K.R. Baker, "Scheduling groups of jobs on a single machine", Operations Research, Vol. 43, pp. 692–703 (1995)

[29] C.C. Wu, and W.C. Lee, "Two-machine flowshop scheduling to minimize mean flow time under linear deterioration", International Journal of Production Economics, Vol.103, pp. 572-584 (2006)

[30] C.C. Wu, and W.C. Lee, "Single-machine group-scheduling problems with deteriorating setup times and job-processing times", International Journal of Production Economics, Vol. 115, pp. 128-133 (2008)

[31] C.C. Wu, Y.R. Shiau, and W.C. Lee, "Single-machine group scheduling problems with deterioration consideration", Computers and Operation Research, Vol. 35, pp. 1652-1659 (2008)

[32] F. Xu, A.X. Guo, J.B. Wang, and F. Shan, "Single machine scheduling problem with linear deterioration under group technology", International Journal of Pure and Applied Mathematics, Vol. 28, pp. 401-406 (2006)