Scheduling a maintenance activity and due-window assignment based on common flow allowance

We study a due-window assignment problem on a single machine. The job-dependent due-windows are obtained by the common flow allowance criterion. The scheduler has the option to perform a maintenance activity which is rate modifying, i.e., improves the processing times of the following jobs. We consider a number of versions of this setting: (i) The maintenance requires a constant time, (ii) The maintenance duration is an increasing function of its starting time (linear deterioration), and (iii) The maintenance duration is position-dependent (general deterioration). We study the standard setting of regular job processing times, and investigate also the extension to position-dependent processing times. The set of potential optimal positions for the maintenance activity is fully characterized. Consequently, the problems based on all the combinations of these settings are shown to be solved in polynomial time.     

Scheduling deteriorating jobs with CON/SLK due date assignment on a single machine

This paper considers the problem of scheduling deteriorating jobs and due date assignment on a single machine. The actual processing time of a job is a linear increasing function of its starting time. The problem is to determine the optimal due dates and the processing sequence simultaneously to minimize costs for earliness, due date assignment and weighted number of tardy jobs. We present polynomial-time algorithms to solve the problem in the case of two popular due date assignment methods: CON and SLK.     

Two-machine flow shop scheduling with deteriorating jobs and chain precedence constraints

In this paper we investigate two-machine flow shop scheduling problems with deteriorating jobs and chain precedence constraints. We consider two types of precedence constraints. Under the first type constraints, a successor cannot start on any machine before its predecessor has been completed on the same machine. Under the second one, a successor cannot start on any machine before its predecessor has been completed on all machines. We show that the problem with the first type precedence constraints is polynomially solvable, and the problem with the second type precedence constraints is NP-hard in the strong sense.     

Simultaneous control of production, repair/replacement and preventive maintenance of deteriorating manufacturing systems

This paper presents a method to find the optimal production, repair/replacement and preventive maintenance policies for a degraded manufacturing system. The system is subject to random machine failures and repairs. The status of the system is deemed to degrade with repair activities. When a failure occurs, the machine is either repaired or replaced, and a replacement action renews the machine, while a repair action brings it to a degraded operational state, with the next repair time increasing as the number of repairs increases as well. A preventive maintenance action is considered in order to improve the reliability of the machine, thereby reducing the amount of disruptions caused by machine failures. The decision variables are the production rate, the preventive maintenance rate and the repair/replacement switching policy upon machine failure. The objective of the study is to find the decision variables that minimize the overall cost, including repair, replacement, preventive maintenance, inventory holding and backlog costs over an infinite planning horizon. The proposed model is based on a semi-Markov decision process, and the stochastic dynamic programming method is used to obtain the optimality conditions. A numerical example is given to illustrate the proposed model, and a sensitivity analysis is considered in order to confirm the structure of the control policy and to illustrate the usefulness of the proposed approach.     

Integrating noncyclical preventive maintenance scheduling and production planning for a single machine

This paper deals with the problem of integrating noncyclical preventive maintenance and tactical production planning for a single machine. We are given a set of products that must be produced in lots during a specified finite planning horizon. The maintenance policy suggests possible preventive replacements at the beginning of each production planning period, and minimal repair at machine failure. The proposed model determines simultaneously the optimal production plan and the instants of preventive maintenance actions. The objective is to minimize the sum of preventive and corrective maintenance costs, setup costs, holding costs, backorder costs and production costs, while satisfying the demand for all products over the entire horizon. The problem is solved by comparing the results of several multi-product capacitated lot-sizing problems. The value of the integration and that of using noncyclical preventive maintenance when the demand varies from one period to another are illustrated through a numerical example and validated by a design of experiment. The later has shown that the integration of maintenance and production planning can reduce the total maintenance and production cost and the removal of periodicity constraint is directly affected by the demand fluctuation and can also reduce the total maintenance and production cost.     

A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system

We analyze a two-machine flow-shop scheduling problem in which the job processing times are controllable by the allocation of resources to the job operations and the resources can be used in discrete quantities. We provide a bicriteria analysis of the problem where the first criterion is to maximize the weighted number of just-in-time jobs and the second criterion is to minimize the total resource consumption cost. We prove that although the problem is known to be NP-hard even for constant processing times, a pseudo-polynomial time algorithm for its solution exists. In addition, we show how the pseudo-polynomial time algorithm can be converted into a two-dimensional fully polynomial approximation scheme for finding an approximate Pareto solution.