An efficient time algorithm for makespan objectives
Loading...
Date
2015
Authors
Yucel Ozturkoglu
Journal Title
Journal ISSN
Volume Title
Publisher
Open Access Color
OpenAIRE Downloads
OpenAIRE Views
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 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.
Description
ORCID
Keywords
Endüstri Mühendisliği
Fields of Science
Citation
[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 scheduling deteriorating 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).
WoS Q
Scopus Q
Source
An International Journal of Optimization and Control: Theories & Applications (IJOCTA)
Volume
5
Issue
2
Start Page
75
End Page
80
Collections
