[An Effective Predictive Maintenance Program of Machines Components]

by

Acknowledgement

I would take this opportunity to thank my research supervisor, family and friends for their support and guidance without which this research would not have been possible.

DECLARATION

I, [type your full first names and surname here], declare that the contents of this dissertation/thesis represent my own unaided work, and that the dissertation/thesis has not previously been submitted for academic examination towards any qualification. Furthermore, it represents my own opinions and not necessarily those of the University.

Signed __________________ Date _________________

Abstract

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.

Table of Contents

ABSTRACT1

CHAPTER I: INTRODUCTION4

Structure of the Dissertation9

Statement of scope and purpose9

Problem description10

Basic properties11

CHAPTER II: THEORETICAL FRAMEWORK12

The nonresumable case12

Property 112

Property 212

Property 313

The resumable case14

Property 414

Property 514

Property 614

SPT algorithm and its performance analysis15

Theorem 115

Theorem 216

Theorem 317

Theorem 418

Dynamic programming19

Branch-and-bound21

Property 723

Property 824

Proposition 125

Proposition 225

Proposition 326

Proposition 426

Proposition 528

Proposition 629

Proposition 730

Proposition 832

Proposition 932

Proposition 1032

Proposition 1133

CHAPTER III: METHODOLOGY34

CHAPTER IV: EXPERIMENTAL RESULTS35

Data generation35

Results36

CHAPTER V: CONCLUSIONS62

REFERENCES63

APPENDIX69

Appendix A. Proof of Theorem 469

Appendix B. Proof of Proposition 870

Appendix C. Proof of Proposition 971

Appendix D. Proof of LB8
An Effective Predictive Maintenance Program of Machines Components

Chapter I: Introduction

Scheduling problems with preventive maintenance have received increasing attention in the last decade, as the importance of the applications has been recognized. (Zhong, 2006) There are two types of preventive maintenance: deterministic maintenance and flexible maintenance. The former means that maintenance periods are determined before jobs are scheduled, i.e., the starting times of the maintenance activities are fixed in advance. Scheduling with this type of maintenance is often referred in literature as “scheduling with availability constraints”, “scheduling with limited machine availability” or “scheduling with fixed non-availability intervals” because during maintenance periods the machine is unavailable for processing any job. The latter means that the schedule of maintenance periods are determined jointly with the schedule of jobs, i.e., the starting times of the maintenance activities are allowed to be flexible ...