An efficient time algorithm for makespan objectives

Yucel Ozturkoglu

Abstract


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 NP-hard 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.

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 NP-hard 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.

Keywords


Scheduling; deteriorating jobs; rate-modifying-activity; single machine; makespan

Full Text:

PDF

References


Browne, S., Yechiali, U., Scheduling deteriorating jobs on a single processor, Operations Research Society, 38, 495-498 (1990). Crossref

Mosheiov, G., V-shaped policies for scheduling deteriorating jobs, Operations Research, 39, 979-991 (1991). Crossref

Kubiak, W., Van de Velde, S., Scheduling deteriorating jobs to minimize makespan, Naval Research Logistics, 45, 511-523 (1998). Crossref

Kovalyov, Y. M., Kubiak, W., A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs, Journal of Heuristics, 3, 287-297 (1998). Crossref

Cheng, T. C. E., Ding, Q., Single machine scheduling with deadlines and increasing rates of processing times, Acta Informatica, 36, 673-692 (2000). Crossref

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).

Lee, C. Y., Leon, V. J., Machine scheduling with a rate-modifying activity, European Journal of Operational Research, 128, 119-128 (2001). Crossref

Lee, C. Y., Lin, C. S., Single-machine scheduling with maintenance and repair rate-modifying activities, European Journal of Operations Research, 135, 493–513 (2001). Crossref

He, Y., Ji, M., Cheng, T. C. E., Scheduling with a restricted rate-modifying activity, Naval Research Logistics, 52:361-369 (2005). Crossref

Mosheiov, G., Sidney, J. B., Scheduling a deteriorating maintenance activity on a single machine, Journal of the Operational Research Society, 61, 882-887 (2010). Crossref

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). Crossref

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). Crossref

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). Crossref

Ozturkoglu, Y., Bulfin, R. L., A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying-activities on a single machine, International Journal of Advanced Manufacturing Technology, 57, 753-762 (2011). Crossref

Ozturkoglu, Y., Bulfin, R. L., Scheduling jobs to consider physiological factors, Human Factors and Ergonomics in Manufacturing & Service Industries, 22(2), 113-120 (2012). Crossref

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). Crossref




DOI: http://dx.doi.org/10.11121/ijocta.01.2015.00260

Refbacks

  • There are currently no refbacks.


Copyright (c) 2015 Yucel Ozturkoglu

Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.

footer_771

   ithe_170     crossref_284         ind_131_43_x_117_117  Scopus  EBSCO_Host    ULAKBIM    PROQUEST   ZBMATH more...