Single-machine scheduling problems with both start-time dependent learning and position dependent aging effects under deteriorating maintenance consideration.

*(English)*Zbl 1202.90149Summary: We introduce a new model of joint start-time dependent learning and position dependent aging effects into single-machine scheduling problems. The machine may need maintenance to improve its production efficiency. The objectives are to find jointly the optimal maintenance position and the optimal sequence such that the makespan, the total completion time, and the total absolute deviation of completion times (TADC) are minimized. We also aim to determine jointly the optimal maintenance position, the optimal due-window size and location, and the optimal sequence to minimize the sum of earliness, tardiness and due-window related costs function. We show that all the studied problems can be optimally solved by polynomial time algorithms.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

90B25 | Reliability, availability, maintenance, inspection in operations research |

90C60 | Abstract computational complexity for mathematical programming problems |

PDF
BibTeX
XML
Cite

\textit{S.-J. Yang}, Appl. Math. Comput. 217, No. 7, 3321--3329 (2010; Zbl 1202.90149)

Full Text:
DOI

**OpenURL**

##### References:

[1] | Bachman, A.; Cheng, T.C.E.; Janiak, J.; Ng, C.T., Scheduling start time dependent jobs to minimize the total weighted completion time, Journal of the operational research society, 53, 688-693, (2002) · Zbl 1059.90063 |

[2] | Biskup, D., A state-of-the-art review on scheduling with learning effects, European journal of operational research, 188, 315-329, (2008) · Zbl 1129.90022 |

[3] | Cheng, T.C.E., Optimal common due-date with limited completion time deviation, Computers & operations research, 15, 91-96, (1988) · Zbl 0635.90050 |

[4] | Cheng, T.C.E., A heuristic for common due-date assignment and job scheduling on parallel machines, Journal of the operational research society, 40, 1129-1135, (1989) · Zbl 0699.90060 |

[5] | Cheng, T.C.E.; Ding, O.; Lin, B.M.T., A concise survey of scheduling with time-dependent processing times, European journal of operational research, 152, 1-13, (2004) · Zbl 1030.90023 |

[6] | Cheng, T.C.E.; Wu, C.-C.; Lee, W.-C., Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects, Information sciences, 178, 2476-2487, (2008) · Zbl 1172.90397 |

[7] | Cheng, T.C.E.; Lai, P.-J.; Wu, C.-C.; Lee, W.-C., Single-machine scheduling with sum-of-logarithm-processing-times-based learning considerations, Information sciences, 179, 3127-3135, (2009) · Zbl 1170.90387 |

[8] | Cheng, T.C.E.; Lee, W.-C.; Wu, C.-C., Scheduling problems with deteriorating jobs and learning effects including proportional setup times, Computers & industrial engineering, 58, 326-331, (2010) |

[9] | Gawiejnowicz, S., Time-dependent scheduling, (2008), Springer-Verlag Inc. New York · Zbl 1155.90004 |

[10] | Gawiejnowicz, S., Scheduling deteriorating jobs subject to job or machine availability constraints, European journal of operational research, 180, 472-478, (2007) · Zbl 1114.90034 |

[11] | Gawiejnowicz, S.; Kononov, A., Complexity and approximability of scheduling resumable proportionally deteriorating jobs, European journal of operational research, 200, 305-308, (2010) · Zbl 1183.90170 |

[12] | Gordon, V.S.; Proth, J.M.; Chu, C., A survey of the state-of-art of common due date assignment and scheduling research, European journal of operational research, 139, 1-25, (2002) · Zbl 1009.90054 |

[13] | Graham, R.L.; Lawler, E.L.; Lenstra, J.K.; Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals discrete mathematics, 5, 287-326, (1979) · Zbl 0411.90044 |

[14] | Hardy, G.H.; Littlewood, J.E.; Polya, G., Inequalities, (1967), Cambridge University Press London · Zbl 0634.26008 |

[15] | Huang, X.; Wang, J.-B.; Wang, L.-Y.; Gao, W.-J.; Wang, X.-R., Single machine scheduling with time-dependent deterioration and exponential learning effect, Computers & industrial engineering, 58, 58-63, (2010) |

[16] | Janiak, A.; Rudek, R., Scheduling problems with position dependent job processing times, (), 26-32 |

[17] | Janiak, A.; Rudek, R., Experience based approach to scheduling problems with the learning effect, IEEE transactions on systems, man, and cybernetics-part A, 39, 344-357, (2009) |

[18] | Janiak, A.; Rudek, R., Scheduling jobs under an aging effect, Journal of the operational research society, 61, 1041-1048, (2010) · Zbl 1196.90048 |

[19] | Ji, M.; Cheng, T.C.E., Scheduling with job-dependent learning effects and multiple rate-modifying activities, Information processing letters, 110, 460-463, (2010) · Zbl 1229.90061 |

[20] | M. Ji, T.C.E. Cheng, Scheduling resumable simple linear deteriorating jobs on a single machine with an availability constraint to minimize makespan, Computers & Industrial Engineering (2010), in press, doi:10.1016/j.cie.2010.08.005. |

[21] | Ji, M.; He, Y.; Cheng, T.C.E., Scheduling linear deteriorating jobs with an availability constraint on a single machine, Theoretical computer science, 362, 115-126, (2006) · Zbl 1100.68009 |

[22] | Kanet, J.J., Minimizing variation of flow time in single machine systems, Management science, 27, 1453-1459, (1981) · Zbl 0473.90048 |

[23] | Kuo, W.-H.; Yang, D.-L., Minimizing the makespan in a single machine scheduling problem with the cyclic process of an aging effect, Journal of the operational research society, 59, 416-420, (2008) · Zbl 1145.90387 |

[24] | Kuo, W.-H.; Yang, D.-L., Parallel-machine scheduling with time dependent processing times, Theoretical computer science, 393, 204-210, (2008) · Zbl 1136.68015 |

[25] | Lee, W.-C.; Wu, C.-C., Multi-machine scheduling with deteriorating jobs and scheduled maintenance, Applied mathematical modelling, 32, 362-373, (2008) · Zbl 1187.90134 |

[26] | Lee, W.-C.; Wu, C.-C., Some single-machine and m-machine flowshop scheduling problems with learning considerations, Information sciences, 179, 3885-3892, (2009) · Zbl 1179.90141 |

[27] | Lee, W.-C.; Lai, P.-J.; Wu, C.-C., Erratum to ‘some single-machine and m-machine flowshop scheduling problems with learning considerations’ [inform. sci. 179 (2009) 3885- 3892], Information sciences, 180, 1073, (2010) |

[28] | Lodree, E.J.; Geiger, C.D., A note on the optimal sequence position for a rate-modifying activity under simple linear deterioration, European journal of operational research, 201, 644-648, (2010) · Zbl 1192.90076 |

[29] | Low, C.; Hsu, C.-J.; Su, C.-T., Minimizing the makespan with an availability constraint on a single machine under simple linear deterioration, Computers & mathematics with applications, 56, 257-265, (2008) · Zbl 1145.90389 |

[30] | Mosheiov, G.; Sarig, A., A due-window assignment problem with position-dependent processing times, Journal of the operational research society, 59, 997-1003, (2008) · Zbl 1144.90391 |

[31] | Mosheiov, G.; Sarig, A., Scheduling a maintenance activity and due-window assignment on a single machine, Computers & operations research, 36, 2541-2545, (2009) · Zbl 1179.90146 |

[32] | Mosheiov, G.; Sidney, J.B., Scheduling a deteriorating maintenance activity on a single machine, Journal of the operational research society, 61, 882-887, (2010) · Zbl 1193.90106 |

[33] | Mosheiov, G.; Sarig, A., Scheduling with a common due-window: polynomially solvable cases, Information sciences, 180, 1492-1505, (2009) · Zbl 1182.90047 |

[34] | Mosheiov, G.; Sarig, A., Scheduling identical jobs and due-window on uniform machines, European journal of operational research, 201, 712-719, (2010) · Zbl 1175.90185 |

[35] | Ng, C.T.; Cheng, T.C.E.; Bachman, A.; Janiak, A., Three scheduling problems with deteriorating jobs to minimize the total completion time, Information processing letters, 81, 327-333, (2002) · Zbl 1059.90063 |

[36] | Sun, L., Single-machine scheduling problems with deteriorating jobs and learning effects, Computers & industrial engineering, 57, 843-846, (2009) |

[37] | Wang, J.-B., Single-machine scheduling problems with the effects of learning and deterioration, Omega, 35, 397-402, (2007) |

[38] | Wang, J.-B., Single machine scheduling with time-dependent learning effect and deteriorating jobs, Journal of the operational research society, 60, 583-586, (2009) · Zbl 1163.90515 |

[39] | Wang, J.-B.; Cheng, T.C.E., Scheduling problems with the effects of deterioration and learning, Asia-Pacific journal of operational research, 24, 245-261, (2007) · Zbl 1121.90066 |

[40] | Wang, J.-B.; Huang, X.; Wang, X.-Y.; Yin, N.; Wang, L.-Y., Learning effect and deteriorating jobs in the single machine scheduling problems, Applied mathematical modelling, 33, 3848-3853, (2009) · Zbl 1205.90137 |

[41] | Wu, C.-C.; Lee, W.-C., Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine, Information processing letters, 87, 89-93, (2003) · Zbl 1161.68367 |

[42] | Yang, D.-L.; Kuo, W.-H., Some scheduling problems with deteriorating jobs and learning effects, Computers & industrial engineering, 58, 25-28, (2010) |

[43] | Yang, S.-J.; Yang, D.-L., Minimizing the makespan on single-machine scheduling with aging effect and variable maintenance activities, Omega, 38, 528-533, (2010) |

[44] | Yang, S.-J.; Yang, D.-L., Single-machine group scheduling problems under the effects of deterioration and learning, Computers & industrial engineering, 58, 754-758, (2010) |

[45] | Yang, S.-J.; Yang, D.-L.; Cheng, T.C.E., Single-machine due-window assignment and scheduling with job-dependent aging effects and deteriorating maintenance, Computers & operations research, 37, 1510-1514, (2010) · Zbl 1183.90203 |

[46] | Yeung, W.K.; Oguz, C.; Cheng, T.E.C., Two-stage flowshop earliness and tardiness machine scheduling involving a common due window, International journal of production economics, 90, 421-434, (2004) |

[47] | Yeung, W.K.; Oguz, C.; Cheng, T.E.C., Two-machine flow shop scheduling with due window to minimize weighted number of early and tardy jobs, Naval research logistics, 56, 593-599, (2009) · Zbl 1183.90206 |

[48] | W.K. Yeung, T.M. Choi, T.C.E. Cheng, Optimal scheduling of a single-supplier single-manufacturer supply chain with common due windows, IEEE Transactions on Automatic Control (2010), in press, doi:10.1109/TAC.2010.2049766. · Zbl 1368.90079 |

[49] | Yin, Y.; Xu, D.; Sun, K.; Li, H., Some scheduling problems with general position-dependent and time-dependent learning effects, Information sciences, 179, 2416-2425, (2009) · Zbl 1166.90342 |

[50] | Zhang, X.; Yan, G., Machine scheduling problems with a general learning effect, Mathematical and computer modelling, 51, 84-90, (2010) · Zbl 1190.90076 |

[51] | Zhao, C.-L.; Tang, H.-Y., Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan, Applied mathematical modelling, 34, 837-841, (2010) · Zbl 1185.90106 |

[52] | C.-L. Zhao, H.-Y. Tang, A note to due-window assignment and single machine scheduling with deteriorating jobs and a rate-modifying activity, Computers & Operations Research (2010), in press, doi:10.1016/j.cor.2010.04.006. · Zbl 1251.90209 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.