Single-Machine Scheduling with Due-Date Assignment and Aging Effect under a DeterioratingMaintenance Activity Consideration

10.6186/IJIMS.2010.21.2.5

Suh-Jenq Yang；Dar-Li Yang；Chou-Jung Hsu

Scheduling ； Due-Date Assignment ； Aging Effect ； Maintenance Activity

International Journal of Information and Management Sciences

21：2（2010 / 06 / 01）

177 - 195

英文

This study investigates single-machine due-date assignment and scheduling problems with a job-dependent aging effect under a deteriorating maintenance activity consideration simul-taneously. The maintenance activity can be scheduled immediately after any one of the jobs has been completed. In order to model the problem more realistic, we assume that: (1) once the maintenance activity has been completed, the machine will revert to its initial condition and the aging effect will start anew, and (2) the machine maintenance duration depends on its starting time. The objective is to find the optimal maintenance position as well as the optimal location of the common due-date for minimizing the total of earliness, tardiness and due-date costs. We introduce a polynomial O(n^4) time solution for the problem. We also present two special cases of the problem and show that they can be optimally solved by a lower order algorithm.

1. Yang, S.-J. and Yang, D.-L., Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities. Omega, in press, 2010.
2. Baker, K. R.,Scudder, G. D.(1990).Sequencing with earliness and tardiness penalties: A review.Operations Research,28,22-35.
3. Biskup, D.(1999).Single-machine scheduling with learning considerations.European Journal of Operational Research,115,173-178.
4. Biskup, D.(2008).A state-of-the-art review on scheduling with learning effects.European Journal of Operational Research,188,315-329.
5. Brucker, P.(2001).Scheduling Algorithms.New York:Springer.
6. Chang, P.-C.,Chen, S.-H.,Mani, V.(2009).A note on due-date assignment and single machine scheduling with a learning/aging effect.International Journal of Production Economics,117,142-149.
7. Chen, J.-S.(2008).Optimization models for the tool change scheduling problem.Omega,36,888-894.
8. Chen, J.-S.,Yang, J.-S.(2007).Alternative models for solving single-machine scheduling with tool changes.International Journal of Information and Management Sciences,18,283-297.
9. Chen, W.-J.(2009).Minimizing number of tardy jobs on a single machine subject to periodic maintenance.Omega,37,591-599.
10. Chen, W.-J.,Tsou, J.-C.(2008).Sequencing heuristic for scheduling jobs with periodic maintenance.International Journal of Information and Management Sciences,19,635-649.
11. Cheng, T. C. E.(1992).Optimal single machine sequencing and assignment of common due-date.Computers & Industrial Engineering,22,115-120.
12. Cheng, T. C. E.,Gupta, M. C.(1989).Survey of scheduling research involving due-date determination decisions.European Journal of Operational Research,38,156-166.
13. Cheng, T. C. E.,Kang, L.,Ng, C. T.(2004).Due-date assignment and single machine scheduling with deteriorating jobs.Journal of the Operational Research Society,55,198-203.
14. Gawiejnowicz, S(2007).Scheduling deteriorating jobs subject to job or machine availability constraints.European Journal of Operational Research,180,472-478.
15. 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.
16. Gordon, V. S.,Tarasevich, A. A.(2009).A note: Common due date assignment for a single machine scheduling with the rate-modifying activity.Computers & Operations Research,36,325-328.
17. 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.
18. Hardy, G. H.,Littlewood, J. E.,Polya, G.(1967).Inequalities.London:Cambridge University Press.
19. Janiak, A.(Ed.)(2006).Scheduling in Computer and Manufacturing Systems.Poland:WKL.
20. Janiak, A.,Rudek, R.(2009).Experience based approach to scheduling problems with the learning effect.IEEE Transactions on Systems, Man, and Cybernetics-Part A,39,344-357.
21. Kubzin, M. A.,Strusevich, V. A.(2006).Planning machine maintenance in two-machine shop scheduling.Operation Research,54,789-800.
22. 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.
23. 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.
24. Lee, C.-L.,Leon, V. J.(2001).Machine scheduling with a rate-modifying activity.European Journal of Operational Research,128,119-128.
25. Ma, Y.,Chu, C.,Zuo, C.(2010).A survey of scheduling with deterministic machine availability constraints.Computers & Industrial Engineering,58(2),199-211.
26. Mosheiov, G.,Oron, D.(2006).Due-date assignment and maintenance activity scheduling problem.Mathematical and Computer Modelling,44,1053-1057.
27. Mosheiov, G.,Sarig, A.(2009).Scheduling a maintenance activity to minimize total weighted completiontime.Computer and Mathematics with Application,57,619-623.
28. Mosheiov, G.,Sidney, J. B.(2010).Scheduling a deteriorating maintenance activity on a single machine.Journal of the Operational Research Society,61(5),882-887.
29. Mosheiov, G.,Sidney, J. B.(2003).Scheduling with general job-dependent learning curves.European Journal of Operational Research,147,665-670.
30. Panwalkar, 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.
31. Papadimitriou, C. H.,Steiglitz, K.(1982).Combinatorial Optimization: Algorithms and Complexity.New Jersey:Prentice-Hall.
32. Schmidt, G.(2000).Scheduling with limited machine availability.European Journal of Operational Research,121,1-15.
33. Yao, M.-J.,Huang, J.-Y.(2007).A global-optimization algorithm for solving the maintenance scheduling problem for a family of machines.International Journal of Information and Management Sciences,18,365-386.

1. Wang, Xiaoqing,Huang, Ling,Cui, Yaodong(2011).Using Layer Patterns in Solving the Two-Dimensional Cutting Stock Problem.International Journal of Information and Management Sciences,22(2),189-199.
2. Wu, Yu-Bin(2014).Parallel Machines Scheduling with Rate-Modifying Activities and Total Absolute Differences Penalties.International Journal of Information and Management Sciences,25(2),407-418.
3. Yang, Suh-Jenq(2012).Scheduling Due Dates Assignment with Simultaneous Considerations of Time-Dependent and Position-Dependent Deterioration Effects and Deteriorating Maintenance on a Single Machine.International Journal of Information and Management Sciences,23(2),257-272.
4. 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.
5. (2012).Scheduling Due Dates Assignment with Simultaneous Considerations of Time-Dependent and Position-Dependent Deterioration Effects and Deteriorating Maintenance on a Single Machine.International Journal of Information and Management Sciences,23(3),257-272.
6. (2012).Unrelated parallel-machine scheduling simultaneously with rate-modifying activities and earliness and tardiness penalties.工業工程學刊,29(4),282-289.
7. (2014).Single-Machine Scheduling Resource-Dependent Deteriorating Jobs with a Learning Effect.International Journal of Information and Management Sciences,25(4),395-405.