Publication Type

Conference Proceeding Article

Publication Date



Standard scheduling theory assumes that all machines are continuously available throughout the planning horizon. In many manufacturing and service management situations however, machines need to be maintained periodically to prevent malfunctions. During the maintenance period, a machine is not available for processing jobs. Hence, a more realistic scheduling model should take into account machine maintenance activities. In this paper, we study the problem of job scheduling with unfixed availability constraints on a single machine. We first propose a preliminary classification for the scheduling problem with unfixed availability constraints based on maintenance constraints, job characteristics and objective function. We divide our analysis into six cases. For each case, we present complexity analysis and exact or approximation algorithms. We also present results of tabu search on NP-hard problem instances. Keywords: Maintenance, Availability, Scheduling.


Artificial Intelligence and Robotics | Business | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Decision Analytics


35th Meeting of the Decision Sciences Institute (DSI)

First Page


Last Page


City or Country

Boston, USA

Additional URL