Generalized stationary models for scheduling single and multiple preventive maintenance routines

This paper is concerned with the development and applicationof stationary models for scheduling single and multiple preventivemaintenance (PM) situations focusing on issues of model implementation.The first part of the paper deals with the practical implementationof the basic single PM scheduling model based on the renewalprocess. The main practical difficulty is lifetime-distributionselection for small data sets which is typical in PM situations.Thus a sensitivity analysis of optimal PM interval to selectedlife distributions following PM and failures (corrective maintenance)is carried out. It has been found that the selected pair ofdistributions using AIC criteria as well as the Weibull–Weibullfitted pair have the smallest availability loss in estimatingthe optimal PM interval. The second part of this paper is concernedwith modelling multi-PM situations—something which hasreceived very little attention in the literature despite itsfrequent implementation in real life. A multi-PM model basedon the renewal process is discussed. The model assumes a multi-PMinterval which is an integer multiple of the single PM intervalsand different renewal functions following each type of PM. Theprocedure of model implementation is discussed through numericalexample.     

A heuristic algorithm for the hospital health examination scheduling problem

This study considers the problem of health examination scheduling. Depending on their gender, age, and special requirements, health examinees select one of the health examination packages offered by a health examination center. The health examination center must schedule all the examinees, working to minimize examinee/doctor waiting time and respect time and resource constraints, while also taking other limitations, such as the sequence and continuity of the examination procedures, into consideration. The Binary integer programming (BIP) model is one popular way to solve this health examination scheduling problem. However, as the number of examinees and health examination procedures increase, solving BIP models becomes more and more difficult, if not impossible. This study proposes health examination scheduling algorithm (HESA), a heuristic algorithm designed to solve the health examination scheduling problem efficiently and effectively. HESA has two primary objectives: minimizing examinee waiting time and minimizing doctor waiting time. To minimize examinee waiting time, HESA schedules the various parts of each examinee’s checkup for times when the examinee is available, taking the sequence of the examination procedures and the availability of the resources required into account. To minimize doctor waiting time, HESA focuses on doctors instead of examinees, assigning waiting examinees to a doctor as soon as one becomes available. Both complexity analysis and computational analyses have shown that HESA is very efficient in solving the health examination scheduling problem. In addition to the theoretical results, the results of HESA’s application to the concrete health examination scheduling problems of two large hospitals in Taiwan are also reported.     

Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance

This paper deals with a single machine scheduling problems with availability constraints. The unavailability of machine results from periodic maintenance activities. In our research, a periodic maintenance consists of several maintenance periods. We consider a machine should stop to maintain after a periodic time interval or to change tools after a fixed amount of jobs processed simultaneously. Each maintenance period is scheduled after a periodic time interval. We study the problems under deterministic environment and flexible maintenance considerations. Preemptive operation is not allowed. In addition, we propose a more reasonable flexible model for the real production settings. The objective is to minimize the makespan. The proposed problem is NP-hard in the strong sense and some heuristic algorithms are provided. The purpose is to present an efficient and effective heuristic algorithm so that it will be straightforward and easy to implement. Computational results show that the proposed algorithm first fit decreasing (DFF) performs well.     

An airline scheduling model and solution algorithms under stochastic demands

When setting a good flight schedule airlines not only have to consider their fleet supply and related operations, as well as market share, but also stochastic variations caused by daily passenger demands in actual operations. Most of the past research on short-term flight scheduling has used the average passenger demand as input to produce the final timetable and schedule, which means that daily passenger variations that occur in actual operations are neglected. To consider such stochastic disturbances we developed a stochastic-demand scheduling model. We employed arc-based and route-based strategies to develop two heuristic algorithms that can be used to solve the model. The test results, based on a major Taiwan airline’s operation, show the good performance of the model and the solution algorithms.     

A bicriteria flowshop scheduling with a learning effect

In many situations, a worker’s ability improves as a result of repeating the same or similar tasks; this phenomenon is known as the learning effect. In this paper the learning effect is considered in a two-machine flowshop. The objective is to find a sequence that minimizes a weighted sum of total completion time and makespan. Total completion time and makespan are widely used performance measures in scheduling literature. To solve this scheduling problem, an integer programming model with n² + 6n variables and 7n constraints where n is the number of jobs is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, the problem with up to 30 jobs can be solved. A heuristic algorithm and a tabu search based heuristic algorithm are presented to solve large size problems. Experimental results show that the proposed heuristic methods can solve this problem with up to 300 jobs rapidly. According to the best of our knowledge, no work exists on the bicriteria flowshop with a learning effect.     

Machine reliability and preventive maintenance planning for cellular manufacturing systems

The paper proposes a preventive maintenance (PM) planning model for the performance improvement of cellular manufacturing systems (CMS) in terms of machine reliability, and resource utilization. In a CMS, parts are processed by a group of interdependent machines, where machine reliability plays an important role in the performance improvement of the cell. Assuming that machine failure times follow a Weibull distribution, the proposed model determines a PM interval and a schedule for performing PM actions on each machine in the cell by minimizing the total maintenance cost and the overall probability of machine failures. The model uses a combined cost and reliability based approach, and optimizes maintenance costs by administering a group maintenance policy subject to a desirable machine reliability threshold. The study also proposes a CMS design model that integrates the above PM concepts into the design process. Illustrative examples are presented to demonstrate the applicability of the proposed approach.     

A new MIP model for mine equipment scheduling by minimizing maintenance cost

Mining investment has been recognized as capital intensive due mainly to the cost of large equipment. Equipment capital costs for a given operation are usually within the order of hundreds of million dollars but may reach to billion dollars for large companies operating multiple mines. Such large investments require the optimum usage of equipment in a manner that the operating costs are minimized and the utilization of equipment is maximized through optimal scheduling. This optimum usage is required to ensure that the business remains sustainable and financially stable. Most mining operations utilize trucks to haul the mined material. Maintenance is one of the major operating cost items for these fleets as it can reach approximately one hundred million dollars yearly. There is no method or application in the literature that optimizes the utilization for truck fleet over the life of mine. A new approach based on mixed integer programming (MIP) techniques is used for annually scheduling a fixed fleet of mining trucks in a given operation, over a multi-year time horizon to minimize maintenance cost. The model uses the truck age (total hours of usage), maintenance cost and required operating hours to achieve annual production targets to produce an optimum truck schedule. While this paper focuses on scheduling trucks for mining operation, concept can be used in most businesses using equipment with significant maintenance costs. A case study for a large scale gold mine showed an annual discounted (10% rate) maintenance cost saving of over $2M and more than 16% ($21M) of overall maintenance cost reduction over 10 years of mine life, compared with the spreadsheet based approach used currently at the operation.     

Exact and heuristic methodologies for scheduling in hospitals: problems, formulations and algorithms

This text summarizes the PhD thesis defended by the author in January 2006 under the supervision of Professor Erik Demeulemeester at the Katholieke Universiteit Leuven. The thesis is written in English and is available from the author’s website (http://www.econ.kuleuven.be/jeroen.belien). In this research we propose a number of exact and heuristic algorithms for various scheduling problems encountered in hospitals. The emphasis lies on the design of new methodologies as well as on the applicability of the algorithms in real-life environments. The main contributions include a new decomposition approach for a particular class of staff scheduling problems, an extensive study of master surgery scheduling algorithms that aim at leveling the resultant bed occupancy and an innovative method for integrating nurse and surgery scheduling.      

An adaptive heuristic algorithm for VLSI test vectors selection

The increasing complexity of today’s system-on-a-chip designs is putting more pressure on the already stressed design verification process. The verification plan must cover several individual cores as well as the overall chip design. Conditions to be verified are identified by the system’s architects, the designers, and the verification team. Testing for these conditions is a must for the design to tape out, especially for high priority conditions. A significant bottleneck in the verification process of such designs is that not enough time is usually given to the final coverage phase, which makes computing cycles very precious. Thus, intelligent selection of test vectors that achieve the best coverage using the minimum number of computing cycles is crucial for on time tape out. This paper presents a novel heuristic algorithm for test vectors selection. The algorithm attempts to achieve the best coverage level while minimizing the required number of computing cycles.     

A global MILP model for FMS scheduling

Flexible manufacturing systems (FMS) require intelligent scheduling strategies to achieve their principal benefit — combining high flexibility with high productivity. A mixed-integer linear programming model (MILP) is presented here for FMS scheduling. The model takes a global view of the problem and specifically takes into account constraints on storage and transportation. Both of these constrained resources are critical for practical FMS scheduling problems and are difficult to model. The MILP model is explained and justified and its complexity is discussed. Two heuristic procedures are developed, based on an analysis of the global MILP model. Computational results are presented comparing the performance of the different solution strategies. The development of iterative global heuristics based on mathematical programming formulations is advocated for a wide class of FMS scheduling problems.     

A bi-level programming model and solution algorithm for the location of logistics distribution centers

In this paper, by considering benefits of customers and logistics planning departments, a bi-level programming model is presented to seek the optimal location for logistics distribution centers. The upper-level model is to determine the optimal location by minimizing the planners’ cost, and the lower gives an equilibrium demand distribution by minimizing the customers’ cost. Based on the special form of constraints, a simple heuristic algorithm is proposed. Finally, a numerical example is used to illustrate the application of the method, which shows that the algorithm is feasible and advantageous.     

Modeling methods and a branch and cut algorithm for pharmaceutical clinical trial planning using stochastic programming

We discuss methods for the solution of a multi-stage stochastic programming formulation for the resource-constrained scheduling of clinical trials in the pharmaceutical research and development pipeline. First, we present a number of theoretical properties to reduce the size and improve the tightness of the formulation, focusing primarily on non-anticipativity constraints. Second, we develop a novel branch and cut algorithm where necessary non-anticipativity constraints that are unlikely to be active are removed from the initial formulation and only added if they are violated within the search tree. We improve the performance of our algorithm by combining different node selection strategies and exploring different approaches to constraint violation checking.     

A polynomial algorithm for an integer quadratic non-separable transportation problem

We study the problem of minimizing the total weighted tardiness when scheduling unti-length jobs on a single machine, in the presence of large sets of identical jobs. Previously known algorithms, which do not exploit the set structure, are at best pseudo-polynomial, and may be prohibitively inefficient when the set sizes are large. We give a polynomial algorithm for the problem, whose number of operations is independent of the set sizes. The problem is reformulated as an integer program with a quadratic, non-separable objective and transportation constraints. Employing methods of real analysis, we prove a tight proximity result between the integer solution to that problem and a fractional solution of a related problem. The related problem is shown to be polynomially solvable, and a rounding algorithm applied to its solution gives the optimal integer solution to the original problem.Supported in part by the National Science Foundation under grant ECS-85-01988, and by the Office of Naval Research under grant N00014-88-K-0377.Supported in part by Allon Fellowship, by Air Force grants 89-0512 and 90-0008 and by DIMACS (Center for Discrete Mathematics and Theoretical Computer Science), a National Science Foundation Science and Technology Center—NSF-STC88-09648. Part of the research of this author was performed in DIMACS Center, Rutgers University.Supported in part by Air Force grant 84-0205.     

Improved algorithm for a generalized on-line scheduling problem on identical machines

This paper considers the problem of on-line scheduling a list of independent jobs in which each job has an arbitrary release time on m parallel identical machines. In this problem, jobs arrive in form of order before its release time and decisions have to be made whenever an order is placed and the orders arrive according to any sequence. A heuristic algorithm, NMLS, better than MLS is given for any m ? 2. The competitive ratio is improved from 2.93920 to 2.78436.     

目标为最小化工件运输时间和的单台机器带一个维修时间段的排序问题的一个改进算法

单台机器带一个维修时间段的排序问题,目标是最小化所有工件的运输时间和.在这篇文章里,重新研究了该问题,并给出了一个时间复杂性为O（n³）的近似算法,将性能比从3/2改进到5/4.     

A market-based multi-agent system model for decentralized multi-project scheduling

We consider a multi-project scheduling problem, where each project is composed of a set of activities, with precedence relations, requiring specific amounts of local and shared (among projects) resources. The aim is to complete all the project activities, satisfying precedence and resource constraints, and minimizing each project schedule length. The decision making process is supposed to be decentralized, with as many local decision makers as the projects. A multi-agent system model, and an iterative combinatorial auction mechanism for the agent coordination are proposed. We provide a dynamic programming formulation for the combinatorial auction problem, and heuristic algorithms for both the combinatorial auction and the bidding process. An experimental analysis on the whole multi-agent system model is discussed.     

A Lagrangian decomposition approach for the pump scheduling problem in water networks

Dynamic pricing has become a common form of electricity tariff, where the price of electricity varies in real time based on the realized electricity supply and demand. Hence, optimizing industrial operations to benefit from periods with low electricity prices is vital to maximizing the benefits of dynamic pricing. In the case of water networks, energy consumed by pumping is a substantial cost for water utilities, and optimizing pump schedules to accommodate for the changing price of energy while ensuring a continuous supply of water is essential. In this paper, a Mixed-Integer Non-linear Programming (MINLP) formulation of the optimal pump scheduling problem is presented. Due to the non-linearities, the typical size of water networks, and the discretization of the planning horizon, the problem is not solvable within reasonable time using standard optimization software. We present a Lagrangian decomposition approach that exploits the structure of the problem leading to smaller problems that are solved independently. The Lagrangian decomposition is coupled with a simulation-based, improved limited discrepancy search algorithm that is capable of finding high quality feasible solutions. The proposed approach finds solutions with guaranteed upper and lower bounds. These solutions are compared to those found by a mixed-integer linear programming approach, which uses a piecewise-linearization of the non-linear constraints to find a global optimal solution of the relaxation. Numerical testing is conducted on two real water networks and the results illustrate the significant costs savings due to optimizing pump schedules.     

An enhanced decomposition algorithm for multistage stochastic hydroelectric scheduling

Handling uncertainty in natural inflow is an important part of a hydroelectric scheduling model. In a stochastic programming formulation, natural inflow may be modeled as a random vector with known distribution, but the size of the resulting mathematical program can be formidable. Decomposition-based algorithms take advantage of special structure and provide an attractive approach to such problems. We develop an enhanced Benders decomposition algorithm for solving multistage stochastic linear programs. The enhancements include warm start basis selection, preliminary cut generation, the multicut procedure, and decision tree traversing strategies. Computational results are presented for a collection of stochastic hydroelectric scheduling problems.     

Parallel machine scheduling with additional resources: Notation,classification, models and solution methods

Majority of parallel machine scheduling studies consider machine as the only resource. However, in most real-life manufacturing environments, jobs may require additional resources, such as automated guided vehicles, machine operators, tools, pallets, dies, and industrial robots, for their handling and processing. This paper presents a review and discussion of studies on the parallel machine scheduling problems with additional resources. Papers are surveyed in five main categories: machine environment, additional resource, objective functions, complexity results and solution methods, and other important issues. The strengths and weaknesses of the literature together with open areas for future studies are also emphasized. Finally, extensions of integer programming models for two main classes of related problems are given and conclusions are drawn based on computational studies.     

Minimizing total tardiness in a scheduling problem with a learning effect

Minimizing of total tardiness is one of the most studied topics on single machine problems. Researchers develop a number of optimizing and heuristic methods to solve this NP-hard problem. In this paper, the problem of minimizing total tardiness is examined in a learning effect situation. The concept of learning effects describes the reduction of processing times arising from process repetition. A 0–1 integer programming model is developed to solve the problem. Also, a random search, the tabu search and the simulated annealing-based methods are proposed for the problem and the solutions of the large size problems with up to 1000 jobs are found by these methods. To the best of our knowledge, no works exists on the total tardiness problem with a learning effect tackled in this paper.