An efficient time algorithm for makespan objectives
DOI:
https://doi.org/10.11121/ijocta.01.2015.00260Keywords:
Scheduling, deteriorating jobs, rate-modifying-activity, single machine, makespanAbstract
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.Downloads
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
Downloads
Published
How to Cite
Issue
Section
License
Articles published in IJOCTA are made freely available online immediately upon publication, without subscription barriers to access. All articles published in this journal are licensed under the Creative Commons Attribution 4.0 International License (click here to read the full-text legal code). This broad license was developed to facilitate open access to, and free use of, original works of all types. Applying this standard license to your work will ensure your right to make your work freely and openly available.
Under the Creative Commons Attribution 4.0 International License, authors retain ownership of the copyright for their article, but authors allow anyone to download, reuse, reprint, modify, distribute, and/or copy articles in IJOCTA, so long as the original authors and source are credited.
The readers are free to:
- Share — copy and redistribute the material in any medium or format
- Adapt — remix, transform, and build upon the material
- for any purpose, even commercially.
- The licensor cannot revoke these freedoms as long as you follow the license terms.
under the following terms:
- Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
- No additional restrictions — You may not apply legal terms or technological measures that legally restrict others from doing anything the license permits.
This work is licensed under a Creative Commons Attribution 4.0 International License.
