×

Single machine scheduling problem with deteriorating maintenance and resource allocation. (Chinese. English summary) Zbl 1424.90080

Summary: This paper studies a single machine scheduling and slack due-date assignment problem with deteriorating maintenance and resource allocation. The actual processing time of a job is a function of the resource amount allocated, position-dependent and time-dependent deterioration effect. In order to counteract the deterioration effect on the machine, we can add a maintenance activity and we assume that at most one maintenance is allowed throughout the planning horizon and the maintenance can be performed immediately after the processing of any job completed, the maintenance duration is dependent on its starting time. The objective is to determine the optimal common slack time, the optimal maintenance position, the optimal resource allocation and the optimal job schedule to minimize the total costs of the earliness and tardiness of the jobs, the common slack time, the makespan and the total completion time under the condition that the total resource amount is limited. According to the related knowledge of convex optimization, we show that the problem is polynomial solvable by transforming it into an assignment problem. We present a polynomial time optimal algorithm to solve the problem.

MSC:

90B35 Deterministic scheduling theory in operations research
90B25 Reliability, availability, maintenance, inspection in operations research
90C27 Combinatorial optimization
91B32 Resource and cost allocation (including fair division, apportionment, etc.)
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI