Scheduling Due Dates Assignment with Simultaneous Considerations of Time-Dependent and Position-Dependent Deterioration Effects and Deteriorating Maintenance on a Single Machine

具時間相依與位置相依退化效應及退化性維修之單機交貨時間指派生產排程研究

10.6186/IJIMS.2012.23.3.2

楊肅正(Suh-Jenq Yang)

生產排程 ； 共同交貨時間指派 ； 剩餘交貨時間指派 ； 退化效應 ； 退化性維修 ； Scheduling ； common due date assignment ； slack due date assignment ； deterioration effects ； deteriorating maintenance

International Journal of Information and Management Sciences

23:3（2012 / 09 / 01）

257 - 272

英文

交貨時間指派為供應鏈管理中深受重要之議題，本研究探討同時考慮工作退化效應與機器退化性維修之單機交貨時間指派生產排程問題，在本研究所提出之模式中，每個工作之加工時間不只與其排序位置有關，亦與機器已運轉之時間相關。考量機器加工之退化效應造成工作完工時間增加，在加工過程中可安排至多一次之維修。本研究考慮共同交貨時間指派與剩餘交貨時間指派兩種模式，目的在找尋機器之最佳維修位置、工作之最佳交貨時間及工作之最佳排序，以使所有工作提早完工、延遲完工與交貨時間總成本為最小。結果顯示，本研究所探討之問題能以多項式時間演算法求解。

The due date assignment has been popular issues related to the interaction between various participants of the supply chain. In this paper, we investigate single machine due dates assignment scheduling problems with deterioration effects and deteriorating maintenance simultaneously. In the proposed model, the actual processing time of a job is not only dependent on the job's scheduled position, it also depends on the time expended by the jobs already processed. To counteract the deterioration effects of the machine, we assume that at most one maintenance is allowed throughout the scheduling horizon. The common due date assignment model and the slack due date assignment model are examined, respectively. The goal is to determine jointly the optimal due dates, the optimal maintenance position, and the optimal schedule to minimize the total penalty function based on earliness, tardiness and due dates. We show that all the problems studied can be optimally solved in polynomial time algorithms.

1. Yang, S. J.,Hsu, C. J.,Yang, D. L.(2010).Single-machine scheduling with due-date assignment and aging effect under a deteriorating maintenance activity consideration.International Journal of Information and Management Sciences,21,177-195.
   連結：
2. Adamopoulos, G. I.,Pappis, C. P.(1996).Single machine scheduling with flow allowances.Journal of the Operational Research Society,47,1280-1285.
3. Cheng, T. C. E.,Ding, Q.,Lin, B. M. T.(2004).A concise survey of scheduling with time dependent processing times.European Journal of Operational Research,152,1-13.
4. Cheng, T. C. E.,Lee, W. C.,Wu, C. C.(2010).Single-machine scheduling with deteriorating functions for job processing times.Applied Mathematical Modelling,34,4171-4178.
5. Gawiejnowicz, S.(2008).Time-Dependent Scheduling.New York:Springer-Verlag Inc..
6. Gawiejnowicz, S.,Kononov, A.(2010).Complexity and approximability of scheduling resumable proportionally deteriorating jobs.European Journal of Operational Research,200,305-308.
7. Gordon, V. S.,Proth, J. M.,Chu, C.(2002).A survey of the state-of-art of common due date assignment and scheduling research.European Journal of Operational Research,139,1-25.
8. Graham, R. L.,Lawler, E. L.,Lenstra, J. K.,Rinnooy Kan, A. H. G.(1979).Optimization and approximation in deterministic sequencing and scheduling: A survey.Annals of Discrete Mathematics,5,287-326.
9. Hardy, G. H.,Littlewood, J. E.,Polya, G.(1967).Inequalities.London:Cambridge University Press.
10. Hsu, C. J.,Yang, S. J.,Yang, D. L.(2011).Two due date assignment problems with position dependent processing time on a single-machine.Computers & Industrial Engineering,60,796-800.
11. Janiak, A.(Ed.)(2006).Scheduling in Computer and Manufacturing Systems.Poland:Warszawa, WKL.
12. Janiak, A.,Rudek, R.(2010).Scheduling jobs under an aging effect.Journal of the Operational Research Society,61,1041-1048.
13. Ji, M.,He, Y.,Cheng, T. C. E.(2006).Scheduling linear deteriorating jobs with an availability constraint on a single machine.Theoretical Computer Science,362,115-126.
14. Jozefowska, J.(2007).Just-in-Time Scheduling: Model and Algorithms for Computer and Manufacturing Systems.New York:Springer-Verlag Inc..
15. Kubzin, M. A.,Strusevich, V. A.(2005).Two-machine flow shop no-wait scheduling with machine maintenance.4OR: A Quarterly Journal of Operations Research,3,303-313.
16. Kubzin, M. A.,Strusevich, V. A.(2006).Planning machine maintenance in two-machine shop scheduling.Operations Research,54,789-800.
17. Kuo, W. H.,Yang, D. L.(2008).A note on due-date assignment and single-machine scheduling with deteriorating jobs.Journal of the Operational Research Society,59,857-859.
18. Lai, P. J.,Lee, W. C.(2010).Single-machine scheduling with a nonlinear deteroration function.Information Processing Letters,110,455-459.
19. Lee, W. C.,Wu, C. C.(2008).Multi-machine scheduling with deteriorating jobs and scheduled maintenance.Applied Mathematical Modelling,32,362-373.
20. Leung, J. Y.(Ed.)(2004).Handbook of Scheduling: Algorithms, Models and Performance Analysis.Boca Raton, FL:CRC Press.
21. Lodree, E. J., Jr.,Geiger, C. D.(2010).A note on the optimal sequence position for a rae-modifying activity under simple linear deterioration.European Journal of Operational Research,201,644-648.
22. Low, C.,Hsu, C. J.,Su, C. T.(2008).Minimizing the makespan with an availability constraint on a single machine under simple linear diterioration.Computers & Mathematics with Applications,56,257-265.
23. Mosheiov, G.,Oron, D.(2006).Due-date assignment and maintenance activity scheduling problem.Mathematical and Computer Modelling,44,1053-1057.
24. Mosheiov, G.,Sidney, J. B.(2010).Scheduling a deteriorating maintenance activity on a single machine.Journal of the Operational Research Society,61,882-887.
25. Panwalker, S. S.,Smith, M. L.,Seidmann, A.(1982).Common due date assignment to minimize total penalty for the one machine scheduling problem.Operations Research,30,391-399.
26. Rudek, A.,Rudek, R.(2011).A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models.Computers & Mathematics with Applications,62,1870-1878.
27. Rudek, R.(2012).Annals of Operations ResearchAnnals of Operations Research,未出版
28. Shabtay, D.(2010).Scheduling and due date assignment to minimize earliness, tardiness, holding due date assignment and batch delivery costs.International Journal of Production Economics,123,235-242.
29. Shabtay, D.,Steiner, G.(2008).The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times.Annals of Operations Research,159,25-40.
30. Wang, J. B.,Guo, Q.(2010).A due-date assignment problem with learning effect and deteriorating jobs.Applied Mathematical Modelling,34,309-313.
31. Wang, J. B.,Huang, X.,Wu, Y. B.,Ji, P.(2012).Group scheduling with independent setuptimes, ready times, and deteriorating job processing times.International Journal of Advanced Manufacturing Technology,60,643-649.
32. Wang, J. B.,Wang, M. Z.(2012).Single-machine scheduling with nonlinear deterioration.Optimization Letters,6,87-98.
33. Wang, J. B.,Wei, C. M.(2011).Parallel machines scheduling with a deteriorating maintenance activity and total absolute differences penalties.Applied Mathematical and Computation,217,8093-8099.
34. Wang, J. J.,Wang, J. B.,Liu, F.(2011).Parallel machines scheduling with a deteriorating maintenance activity.Journal of the Operational Research Society,62,1898-1902.
35. Wang, X. Y.,Wang, M. Z.(2010).Single machine common flow allowance scheduling with a rate-modifying activity.Computers & Industrial Engineering,59,898-902.
36. Wu, C. C.,Lee, W. C.(2003).Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine.Information Processing Letters,87,89-93.
37. Wu, Y. B.(2011).Parallel machines scheduling rate-modifying activities and total absolute differences penalties.International Journal of Information and Management Sciences,22,407-418.
38. Wu, Y. B.(2011).Single-machine scheduling resource-dependent deteriorating jobs with a learning effect.International Journal of Information and Management Sciences,22,395-405.
39. Yang, S. j.,Yang, D. L.(2010).Single-machine scheduling problems with aging/deteriorating effect under an optional maintenance activity consideration.INFOR: Information Systems and Operational Research,48,171-179.
40. Zhao, C. L.,Tang, H. Y.,Cheng, C. D.(2009).Two-parallel machines scheduling with rate-modifying activities to minimize total completion time.European Journal of Operational Research,198,354-357.

1. Yang, Suh-Jenq,Lai, Chien-Jung(2014).Scheduling with Multiple Common Due Windows Assignment and General Position-Dependent and Resource-Dependent Processing Times.International Journal of Information and Management Sciences,25(2),101-120.