An efficient time algorithm for makespan objectives
This paper focuses on a single machine scheduling subject to machine deterioration with rate-modifying activities (RMA). The motivation for this study stems from the automatic-production line problem with one machine. The main question is to find the sequence in which jobs should be scheduled, how many maintenance activity (RMA) to use, if any, and where to insert them in the schedule during the time interval with optimal makespan objective. This problem is known to be NPhard and we give concise analyses of the problem and provide polynomial time algorithms to solve the makespan problem. We also propose an algorithm which can be applied to some scheduling problems with the actual processing time of job nonlinearly based on its position
[1] Browne, S., Yechiali, U., Scheduling deteriorating jobs on a single processor, Operations Research Society, 38, 495-498 (1990).
[2] Mosheiov, G., V-shaped policies for scheduling deteriorating jobs, Operations Research, 39, 979-991 (1991).
[3] Kubiak, W., Van de Velde, S., Scheduling deteriorating jobs to minimize makespan, Naval Research Logistics, 45, 511-523 (1998).
[4] Kovalyov, Y. M., Kubiak, W., A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 3, 287-297 (1998).
[5] Cheng, T. C. E., Ding, Q., Single machine scheduling with deadlines and increasing rates of processing times, Acta Informatica, 36, 673-692 (2000).
[6] Qi, X., Chen, T., Tu, F., Scheduling with the maintenance on a single machine, Working Paper, Department of Computer System Sciences, Nankai University, China (1997).
[7] Lee, C. Y., Leon, V. J., Machine scheduling with a rate-modifying activity, European Journal of Operational Research, 128, 119-128 (2001).
[8] Lee, C. Y., Lin, C. S., Single-machine scheduling with maintenance and repair ratemodifying activities, European Journal of Operations Research, 135, 493–513 (2001).
[9] He, Y., Ji, M., Cheng, T. C. E., Scheduling with a restricted rate-modifying activity, Naval Research Logistics, 52:361-369 (2005).
[10] Mosheiov, G., Sidney, J. B., Scheduling a deteriorating maintenance activity on a single machine, Journal of the Operational Research Society, 61, 882-887 (2010).
[11] Gordon, V. S., Tarasevich, A. A., A note: common due date assignment for a single machine scheduling with the rate-modifying activity, Computer Operations Research, 36, 325-328 (2009).
[12] Wang, X. Y., Wang, M. Z., Single machine common flow allowance scheduling with a rate-modifying activity, Computers and Industrial Engineering, 59, 898-902 (2010).
[13] 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).
[14] Ozturkoglu, Y., Bulfin, R. L., A unique integer mathematical model for schedulingdeteriorating jobs with rate-modifyingactivities on a single machine, International Journal of Advanced Manufacturing Technology, 57, 753-762 (2011).
[15] Ozturkoglu, Y., Bulfin, R. L., Scheduling jobs to consider physiological factors, Human Factors and Ergonomics in Manufacturing & Service Industries, 22(2), 113-120 (2012).
[16] Graham, R. L., Lawler, E. L., Lenstra, J. K., Rinnooy, K. A. H. G., Optimization and approximation in deterministic sequencing and scheduling: A Survey, Annals of Discrete Mathematics, 5, 287–326 (1979)