Single-machine scheduling with periodic maintenance to minimize makespan

We consider a single-machine scheduling problem with periodic maintenance activities. Although the scheduling problem with maintenance has attracted researchers’ attention, most of past studies considered only one maintenance period. In this research several maintenance periods are considered where each maintenance activity is scheduled after a periodic time interval. The objective is to find a schedule that minimizes the makespan, subject to periodic maintenance and nonresumable jobs. We first prove that the worst-case ratio of the classical LPT   algorithm is 2. Then we show that there is no polynomial time approximation algorithm with a worst-case ratio less than 2 unless P=NP$P=\text{<italic>NP</italic>}$, which implies that the LPT algorithm is the best possible.     

Performance analysis of periodic and concurrent data structuremaintenance strategies for network servers

Three strategies for designing servers and maintaining their data structures are discussed: incremental maintenance, periodic maintenance, and concurrent maintenance. The authors study periodic and concurrent maintenance strategies analytically in order to gain more insight into the behavior of servers using these strategies and determine when and how the maintenance should be performed. For periodic maintenance, it is shown that there is a value of the period which minimizes the average response time, and a formula to compute this value analytically is derived. For concurrent maintenance, a formula for its average response time and the condition under which concurrent maintenance would be preferable to periodic maintenance is derived. The authors have conducted a series of experiments to compare the performance of different maintenance strategies. For the system considered in the experiment, periodic maintenance yields the best average response time, whereas concurrent maintenance gives the least standard deviation and the smallest maximum response time     

Stabilization of decentralized control systems by means of periodic feedback

This paper deals with structurally constrained periodic control design for interconnected systems. It is assumed that the system is linear time-invariant (LTI), observable and controllable, and that its modes are distinct and nonzero. It is shown that the notions of a quotient fixed mode (QFM) and a structured decentralized fixed mode (SDFM) are equivalent for this class of systems. Then, it is proved that if the system is decentrally stabilizable, then one candidate for the decentralized stabilizing controller is a time-varying one consisting of a decentralized LTI discrete-time compensator and a zero-order hold. More specifically, the non-quotient fixed modes of the system will be eliminated via sampling for almost all sampling periods, while any QFM will still remain a fixed mode. The results obtained are ultimately extended to the case when the system has some repeated modes, none of which is a DFM.     

A hybrid genetic algorithm to minimize the periodic preventive maintenance cost in a series-parallel system

This study presents a hybrid genetic algorithm (GA) to optimize the periodic preventive maintenance model in a series-parallel system. The intrinsic properties of a repairable system, including the structure of reliability block diagrams, maintenance priority of components, and their maintenance periods, are considered in developing the proposed hybrid GA. The importance measure of components is employed to account for these properties, identify important components, and determine their maintenance priorities. The optimal maintenance periods of these important components are then determined to minimize total maintenance cost given the allowable worst reliability of a repairable system using the GA search mechanism. An elitist conservation strategy is applied to retain superior chromosomes in the iterative breeding process to accelerate the approach toward the global optimum. Furthermore, the response surface methodology is utilized to systematically determine crossover probability and mutation probability in the GA instead of using the conventional trial-and-error process. A case study demonstrates the effectiveness and practicality of the proposed hybrid GA in optimizing the periodic preventive maintenance model in a series-parallel system.     

On reliability of systems with periodic maintenance under rare failures of its elements

There is investigated a model of a system with the highly reliable elements, in which the periods of functioning are changed by the periods of maintenance. The system must be operational only in the periods of functioning although the restoration in these periods is not produced. The system is completely restored in the nearest period of maintenance. Since the elements of system are highly reliable, the reserve of system is rarely exhausted during each period of functioning. Therefore it is possible to use the results, obtained for the systems with fast restoration, for the reliability assessment of system, which is not restorable in the periods of the functioning. The estimations of indices of failure-free performance and maintainability of such systems are obtained.     

Minimizing total completion time on a single machine with a flexible maintenance activity

A problem of jointly scheduling multiple jobs and a single maintenance activity on a single machine with the objective of minimizing total completion time is considered in this paper. It is assumed that the machine should be stopped for maintenance which takes a constant duration within a predefined period. The problem is generalized from the one with a fixed maintenance in that it relaxes the starting time of the maintenance from a fixed time point to a predefined period. Both resumable and nonresumable cases are studied. First, three properties of an optimal solution to each of the two cases are identified. Then it is shown that the proposed shortest processing time (SPT) algorithm is optimal for the resumable case. As for the nonresumable case, the conditions under which the SPT algorithm is optimal are also specified. Furthermore, it is shown that relaxing the starting time of the maintenance cannot improve the relative error bound of the SPT algorithm. The focus of the paper is presented afterwards, which is to develop a dynamic programming algorithm and a branch-and-bound algorithm to generate an optimal solution for this case. Experimental results show that these algorithms are effective and complementary in dealing with different instances of the problem.     

An effective heuristic for flexible job-shop scheduling problem with maintenance activities

Most production scheduling problems, including the standard flexible job-shop scheduling problem (FJSP), assume that machines are continuously available. However, in most realistic situations, machines may become unavailable during certain periods due to preventive maintenance (PM). In this paper, a flexible job-shop scheduling problem with machine availability constraints is considered. Each machine is subject to preventive maintenance during the planning period and the starting times of maintenance activities are either flexible in a time window or fixed beforehand. Moreover, two cases of maintenance resource constraint are considered: sufficient maintenance resource available or only one maintenance resource available. To deal with this variant FJSP problem with maintenance activities, a filtered beam search (FBS) based heuristic algorithm is proposed. With a modified branching scheme, the machine availability constraint and maintenance resource constraint can be easily incorporated into the proposed algorithm. Simulation experiments are conducted on some representative problems. The results demonstrate that the proposed filtered beam search based heuristic algorithm is a viable and effective approach for the FJSP with maintenance activities.     

Nearly optimal perfectly periodic schedules

We consider the problem of scheduling a set of pages on a single broadcast channel using time-multiplexing. In a perfectly periodic schedule, time is divided into equal size slots, and each page is transmitted in a time slot precisely every fixed interval of time (the period of the page). We study the case in which each page i has a given demand probability , and the goal is to design a perfectly periodic schedule that minimizes the average time a random client waits until its page is transmitted. We seek approximate polynomial solutions. Approximation bounds are obtained by comparing the costs of a solution provided by an algorithm and a solution to a relaxed (non-integral) version of the problem. A key quantity in our methodology is a fraction we denote by , that depends on the maximum demand probability: . The best known polynomial algorithm to date guarantees an approximation of . In this paper, we develop a tree-based methodology for perfectly periodic scheduling, and using new techniques, we derive algorithms with better bounds. For small values, our best algorithm guarantees approximation of . On the other hand, we show that the integrality gap between the cost of any perfectly periodic schedule and the cost of the fractional problem is at least . We also provide algorithms with good performance guarantees for large values of . Received: December 2001 / Accepted: September 2002     

Patient scheduling with periodic deteriorating maintenance on single medical device

In this paper, we study a patient scheduling problem with periodic deteriorating maintenance. The objective is to minimize the number of tardy medical treatment of all the patients. A binary integer programming model is developed to characterize the problem. A three-phase heuristic based on Moore׳s algorithm is proposed for the problem. Numerical experiments are performed to demonstrate the effectiveness of the proposed heuristic. Results show that the proposed heuristic is able to obtain a relatively good solution in a short computation time. The impact of the key parameters on the performance of the proposed heuristic is discussed. Finally, we develop an earliest due date (EDD) rule based heuristic to optimize another objective, the maximum tardiness, which is more applicable when fairness among patients is considered.     

An efficient approach for the multiprocessor non-preemptive strictly periodic task scheduling problem

Strict periodicity constraint is of great importance since it concerns some hard real-time systems where missing deadlines leads to catastrophic situations. However, the problem of schedulability analysis for non-preemptive strictly periodic tasks on a multiprocessor platform is even more intractable than the one with the common periodicity. In order to implement such systems, designers need effective tools based on fast and near-optimal solutions.This paper presents a schedulability analysis which results mainly in a, two versions, task assignment and start-time calculation algorithm. The first one targets the harmonic task periods case while the second one targets the non-harmonic task periods case. Each version is based on a sufficient uniprocessor schedulability test. In addition, for the non-harmonic case which is the most intractable, the uniprocessor sufficient schedulability test uses the strictly periodic task utilization factor. This factor stands for the fraction of time spent to execute a task while its strict periodicity and the ones of the already scheduled tasks are met. As a result, an efficient and easily implementable scheduling algorithm is proposed which begins by assigning tasks to processors then attributes a start-time to every task in such a way that strict periodicity and deadline constraints are met. The effectiveness of the proposed scheduling algorithm, in both versions, has been shown by a performance evaluation and comparisons with an optimal and a similar suboptimal solution.     

Vector field editing and periodic orbit extraction using Morse decomposition

Design and control of vector fields is critical for many visualization and graphics tasks such as vector field visualization, fluid simulation, and texture synthesis. The fundamental qualitative structures associated with vector fields are fixed points, periodic orbits, and separatrices. In this paper, we provide a new technique that allows for the systematic creation and cancellation of fixed points and periodic orbits. This technique enables vector field design and editing on the plane and surfaces with desired qualitative properties. The technique is based on Conley theory, which provides a unified framework that supports the cancellation of fixed points and periodic orbits. We also introduce a novel periodic orbit extraction and visualization algorithm that detects, for the first time, periodic orbits on surfaces. Furthermore, we describe the application of our periodic orbit detection and vector field simplification algorithms to engine simulation data demonstrating the utility of the approach. We apply our design system to vector field visualization by creating data sets containing periodic orbits. This helps us understand the effectiveness of existing visualization techniques. Finally, we propose a new streamline-based technique that allows vector field topology to be easily identified.     

Minimization of the life cycle cost for a multistate system under periodic maintenance

Although preventive maintenance policies have received extensive interest, limited attention has been paid to implementing multiple maintenance actions for a multistate system over a finite horizon in continuous time. Therefore, this study closely examines such maintenance actions by viewing a coherent multicomponent system as a multistate system and assuming that the necessary maintenance action and cost which move the current state to an extremely better state depends on the current state. The above problem is also formulated as a periodic maintenance model. In addition, the model's characteristics are elucidated to obtain the optimal cycle time of maintenance actions, thereby minimizing the life cycle cost over a specific finite horizon.     

基于预防维护的单机调度问题

在两种维护约束下,研究完工时间之和最小化的单机调度问题.第1种维护约束是,固定周期预防维护;第2种维护约束是,机器工作期间可连续加工的最大工件个数受限.对于这种带有约束的调度问题,根据问题的规模,采用4种方法进行求解.针对小规模问题,建立一个二值整数规划模型,并根据最优解的特性制定剪枝规则,进而给出分支定界算法.针对中...     

Error growth in the numerical integration of periodic orbits

This paper is concerned with the long term behaviour of the error generated by one step methods in the numerical integration of periodic flows. Assuming numerical methods where the global error possesses an asymptotic expansion and a periodic flow with the period depending smoothly on the starting point, some conditions that ensure an asymptotically linear growth of the error with the number of periods are given. A study of the error growth of first integrals is also carried out. The error behaviour of Runge–Kutta methods implemented with fixed or variable step size with a smooth step size function, with a projection technique on the invariants of the problem is considered.     

Scheduling jobs under increasing linear machine maintenance time

Although scheduling problems with machine availability have attracted many researchers’ attention, most of the past studies are mainly focused on one or several prefixed machine maintenance activities. In this research, we assume that the time needed to perform one maintenance activity is an increasing linear function of the total processing time of the jobs that are processed after the machine’s last maintenance activity. We consider two scheduling problems with such maintenance requirement in this paper. The first problem is a parallel machine scheduling problem where the length of the time interval between any two consecutive maintenance activities is between two given positive numbers. The objective is to minimize the maintenance makespan, i.e., the completion time of the last finished maintenance. The second problem is a single machine scheduling problem where the length of the time interval between any two consecutive maintenance activities is fixed and the objective is to minimize the makespan, i.e., the completion time of the last finished job. We propose two approximation algorithms for the considered problems and analyze their performances.     

Inspection and maintenance planning: an application of semi-Markov decision processes

In this paper, we consider a system which deteriorates stochastically from one time unit to another. The state of the system, which is a continuous random variable, can be observed only by inspection. The goal of this paper is to derive a predictive maintenance policy which indicates, at each inspection and according to the observed value, whether a preventive maintenance is necessary and when the next inspection should be done. The objective is to minimize the long-run average cost incurred by inspections, preventive maintenance and unexpected breakdowns. The problem is modelled by a semi-Markov decision process. Analytical properties are derived, and based on these properties, numerical methods are constructed to compute an optimal policy.     

Optimal control of a resource-sharing multiprocessor with periodic maintenance

Shared resources and the processes that control them play a critical role in the functioning of concurrent systems. The article analyzes the production control of a workstation producing a number of products concurrently. The workstation is periodically stopped for maintenance. The objective of the production control is to minimize inventory and backlog costs over an infinite time horizon. Using the maximum principle and under the so-called agreeable cost structure, we derive the optimal production control. We prove that under this cost structure, the problem can be solved in polynomial time.     

Finding anomalous periodic time series

Catalogs of periodic variable stars contain large numbers of periodic light-curves (photometric time series data from the astrophysics domain). Separating anomalous objects from well-known classes is an important step towards the discovery of new classes of astronomical objects. Most anomaly detection methods for time series data assume either a single continuous time series or a set of time series whose periods are aligned. Light-curve data precludes the use of these methods as the periods of any given pair of light-curves may be out of sync. One may use an existing anomaly detection method if, prior to similarity calculation, one performs the costly act of aligning two light-curves, an operation that scales poorly to massive data sets. This paper presents PCAD, an unsupervised anomaly detection method for large sets of unsynchronized periodic time-series data, that outputs a ranked list of both global and local anomalies. It calculates its anomaly score for each light-curve in relation to a set of centroids produced by a modified k-means clustering algorithm. Our method is able to scale to large data sets through the use of sampling. We validate our method on both light-curve data and other time series data sets. We demonstrate its effectiveness at finding known anomalies, and discuss the effect of sample size and number of centroids on our results. We compare our method to naive solutions and existing time series anomaly detection methods for unphased data, and show that PCAD’s reported anomalies are comparable to or better than all other methods. Finally, astrophysicists on our team have verified that PCAD finds true anomalies that might be indicative of novel astrophysical phenomena.     

Linear periodic controller design for decentralized control systems

In the decentralized control of linear time-invariant (LTI) systems, a decentralized fixed mode (DFM) is a system mode which is immoveable using an LTI controller, while a quotient DFM (QDFM) is one which is immoveable using any form of nonlinear time-varying compensation. If a system has no unstable DFMs, there are well-known procedures for designing an LTI stabilizing controller; for systems which have unstable DFMs but no unstable QDFMs, we provide a simple design algorithm which yields a linear periodic sampled-data stabilizing controller.     

Mining asynchronous periodic patterns in time series data

Periodicy detection in time series data is a challenging problem of great importance in many applications. Most previous work focused on mining synchronous periodic patterns and did not recognize the misaligned presence of a pattern due to the intervention of random noise. In this paper, we propose a more flexible model of asynchronous periodic pattern that may be present only within a subsequence and whose occurrences may be shifted due to disturbance. Two parameters min/spl I.bar/rep and max/spl I.bar/dis are employed to specify the minimum number of repetitions that is required within each segment of nondisrupted pattern occurrences and the maximum allowed disturbance between any two successive valid segments. Upon satisfying these two requirements, the longest valid subsequence of a pattern is returned. A two-phase algorithm is devised to first generate potential periods by distance-based pruning followed by an iterative procedure to derive and validate candidate patterns and locate the longest valid subsequence. We also show that this algorithm cannot only provide linear time complexity with respect to the length of the sequence but also achieve space efficiency.