Open AccessAn efficient time algorithm for makespan objectives
Author(s) -
Yücel Öztürkoğlu
Publication year - 2015
Publication title -
an international journal of optimization and control: theories and applications/e-an international journal of optimization and control: theories and applications
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.287
H-Index - 6
eISSN - 2146-5703
pISSN - 2146-0957
DOI - 10.11121/ijocta.01.2015.00260
Subject(s) - job shop scheduling , computer science , time complexity , schedule , scheduling (production processes) , mathematical optimization , algorithm , single machine scheduling , approximation algorithm , mathematics , operating system
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.