Integration of production planning and scheduling using an expert system and a genetic algorithm

In the traditional approaches, processes of planning and scheduling are done sequentially, where the process plan is determined before the actual scheduling is performed. This simple approach ignores the relationship between the scheduling and planning. Practical scheduling systems need to be able to react to significant real-time events within an acceptable response time and revise schedules appropriately. Therefore, the author proposes a new methodology with artificial intelligence to support production planning and scheduling in supply net. In this approach, the production planning problem is first solved, and then the scheduling problem is considered with the constraint of the solution. The approach is implemented as a combination of expert system and genetic algorithm. The research indicates that the new system yields better results in real-life supply net than using a traditional method. The results of experiments provide that the proposed genetic algorithm produces schedules with makespan that is average 21% better than the methods based on dispatching rules.     

A SEQUENTIAL APPROACH TO DERIVATION OF STAND TREATMENT AND FOREST-WIDE HARVEST PRESCRIPTION OR SUPPLY

Current methods for optimization of stand treatment and forest-wide harvest scheduling use mathematical programming that presumes perfect information on production, costs, and revenues over long planning periods. These approaches simultaneously optimize harvest for all periods in the planning horizon. In contrast, the method presented here assumes that stand-level planning and harvest scheduling proceed sequentially rather than simultaneously over every period. A backward-recursion dynamic program is used to determine the discounted net value of a wide range of current harvest strategies for each stand class in the forest inventory on the basis of a projected set of optimal treatments for future harvest and regeneration of each stand. The most highly valued strategy is selected if there are no volume constraints. Otherwise, suboptimal harvest alternatives are ranked in order of increasing opportunity cost for increasing or decreasing harvest; constraints met only up to a maximum opportunity cost is also demonstrated.     

Modeling target volume flows in forest harvest scheduling subject to maximum area restrictions

In forest harvest scheduling problems, one must decide which stands to harvest in each period during a planning horizon. A typical requirement in these problems is a steady flow of harvested timber, mainly to ensure that the industry is able to continue operating with similar levels of machine and labor utilizations. The integer programming approaches described use the so-called volume constraints to impose such a steady yield. These constraints do not directly impose a limit on the global deviation of the volume harvested over the planning horizon or use pre-defined target harvest levels. Addressing volume constraints generally increases the difficulty of solving the integer programming formulations, in particular those proposed for the area restriction model approach. In this paper, we present a new type of volume constraint as well as a multi-objective programming approach to achieve an even flow of timber. We compare the main basic approaches from a computational perspective. The new volume constraints seem to more explicitly control the global deviation of the harvested volume, while the multi-objective approach tends to provide the best profits for a given dispersion of the timber flow. Neither approach substantially changed the computational times involved.     

A Common Error in Production Scheduling

Many production scheduling systems use schedules of planned start/finish times for jobs up to a given planning horizon which includes the period between rescheduling operations. The integrity and usefulness of such schedules depends on the accuracy of the estimated time data which is available on the operations to be performed.There is a widespread belief that "on the average" if errors in the estimated time data are not biased then they will balance out and the schedules will give a reasonable plan for the period between rescheduling operations. This paper uses the elementary theory of the simple random walk to show that this assumption is not valid and that scheduling systems based upon it will not make sufficient allowance for the relatively highly probable events of permanent under-schedule or over-schedule conditions.     

A heuristic methodology for sizing a large-scale system of constrained, reusable resources

This paper proposes a methodology for sizing certain large-scale systems of reusable, capacity-constrained resources engaged in tasks of varying duration. A heuristic program schedules resources throughout a finite planning horizon using two decision variables: varying resource capacity for meeting demand and varying task duration. A model of the problem and heuristic scheduling program are presented. A sequential, iterative sizing procedure determines the number of system resources to meet demand at each stage of the problem. Results compare the methodology with heuristics used in practice to schedule resources and size a real-world, large-scale training system.     

Pavement rehabilitation scheduling and toll pricing under different regulatory regimes

This paper addresses the highway pavement rehabilitation scheduling and toll pricing issues over a planning horizon. In the highway system concerned, two types of agents are considered, namely highway operator and road users. Two models, which account for different highway regulatory regimes (i.e. public and private), are proposed. In the public regulatory model, the government aims to maximize total discounted social welfare of the transportation system over the planning horizon by determining the optimal pavement rehabilitation schedule and toll level. In the private regulatory regime, a profit-driven private operator seeks to optimize the pavement rehabilitation schedule and toll level to maximize its own discounted net profit over the planning horizon. The proposed models treat the interactions between the highway operator and the road users in the system as a bi-level hierarchical problem in which the upper level is a multi-period pavement rehabilitation scheduling and toll pricing problem, while the lower level is a multi-period route choice equilibrium problem. A heuristic solution algorithm that combines a greedy approach and a sensitivity analysis based approach is developed to solve the proposed bi-level multi-period optimization models. An illustrative example is used to show the applications of the proposed models. The findings show that the highway regulatory regime, pavement deterioration parameter and the roughness-induced vehicle operating cost can significantly affect the pavement rehabilitation schedules and the toll level as well as the performance of transportation system in terms of total life-cycle travel demand, net profit and social welfare.     

Dynamic transport scheduling under multiple resource constraints

This paper presents a heuristic for the dynamic vehicle scheduling problem with multiple resource capacity constraints. In the envisaged application, an automated transport system using Automated Guided Vehicles, bottleneck resources are (1) vehicles, (2) docks for loading/unloading, (3) vehicle parking places, and (4) load storage space. This problem is hard, because interrelated activities (loading, transportation, unloading) at several geographical locations have to be scheduled under multiple resource constraints, where the bottleneck resource varies over time. Besides, the method should be suitable for real-time planning. We developed a dedicated serial scheduling method and analyzed its dynamic behavior using discrete event simulation. We found that our method is very well able to find good vehicle schedules satisfying all resource constraints. For comparison, we used a simple approach where we left out the resource constraints and extended the processing times by statistically estimated waiting times to account for finite capacities. We found that our newly designed method finds better schedules in terms of service levels.     

Preventive maintenance scheduling of multi-cogeneration plants using integer programming

Maintenance scheduling of cogeneration plants, which produce both electric power and desalinated water, is a typical complex process with long-term operations and planning problems. The plants' maintenance scheduling process has to determine the appropriate schedule for preventive maintenance, while satisfying all the system constraints and maintaining adequate system availability. It is an optimization problem and the maintenance and system constraints include the crew constraint, maintenance window constraint and time limitation constraint. In this paper, an integer linear-programming model, which has been developed, is described which schedules the preventive maintenance tasks in a multi-cogeneration plant. Results of a test example of such a plant situated in Kuwait are presented to show the applicability of the approach.     

Power-aware scheduling of preemptable jobs on identical parallel processors to minimize makespan

This paper deals with power-aware scheduling of preemptable jobs on identical parallel processors to minimize schedule length when jobs are described by continuous, strictly concave functions relating their processing speed at time t to the amount of power allotted at the moment. Power is a continuous, doubly constrained resource, i.e. both: its availability at time t and consumption over scheduling horizon are constrained. Precedence constraints among jobs are represented by a task-on-arc graph. A methodology based on properties of optimal schedules is presented for solving the problem optimally for a given ordering of nodes in the graph. Heuristics for finding an ordering which leads to possibly short schedules are proposed and examined experimentally.     

A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing

This paper presents a lexicographic approach and integer programming formulations for a dual-objective, long-term production scheduling in make-to-order manufacturing environment. The problem objective is to assign single-period customer orders for various product types to planning periods to complete all the orders with minimum number of tardy orders as a primary criterion and to level the aggregate production or the total capacity utilization over a planning horizon as a secondary criterion. Each order must be completed during one planning period. The basic integer programming formulation has been strengthened by the addition of some cutting constraints derived by relating the demand on required capacity to available capacity for each subset of orders with the same due date. The approach has been applied to optimize production schedules in a flexible flowshop made up of several processing stages in series, with identical, parallel machines, and an output buffer of limited capacity for holding completed products before delivery to the customers. Numerical examples modeled after a real-world make-to-order flexible assembly line in the electronics industry are provided and some computational results are reported.     

A decomposed branch-and-price procedure for integrating demand planning in personnel staffing problems

The personnel staffing problem calculates the required workforce size and is determined by constructing a baseline personnel roster that assigns personnel members to duties in order to cover certain staffing requirements. In this research, we incorporate the planning of the duty demand in the staff scheduling problem in order to lower the staffing costs. More specifically, the demand originates from a project scheduling problem with discrete time/resource trade-offs, which embodies additional flexibility as activities can be executed in different modes. In order to tackle this integrated problem, we propose a decomposed branch-and-price procedure. A tight lower and upper bound are calculated using a problem formulation that models the project scheduling constraints and the time-related resource scheduling constraints implicitly in the decision variables. Based upon these bounds, the strategic problem is decomposed into multiple tactical subproblems with a fixed workforce size and an optimal solution is searched for each subproblem via branch-and-price. Fixing the workforce size in a subproblem facilitates the definition of resource capacity cuts, which limit the set of eligible project schedules, decreasing the size of the branching tree. In addition, in order to find the optimal integer solution, we propose a specific search strategy based upon the lower bound and dedicated rules to branch upon the workload generated by a project schedule. The computational results show that applying the proposed search space decomposition and the inclusion of resource capacity cuts lead to a well-performing procedure outperforming different other heuristic and exact methodologies.     

ARMMS: Analogical reasoning model management system for multicriteria vehicle scheduling

The transportation industry problem of scheduling vehicles combines the spatial characteristics of routing with time domain considerations of activity schedules. The problem is complex because of the numerous interacting constraints in the spatial and time domains. Further, some of the constraints are flexible and some arise in real-time. The scheduling problem is often presented with multiple objectives that are not all economic in nature and which can be contradictory to one another. In response to these needs, this paper describes an analogical reasoning model management system, called ARMMS, designed in the domain of vehicle scheduling. ARMMS consists of knowledge bases and data bases, a truth maintenance system, a user interface, an inference engine, a learning mechanism, and a model library. Given a scheduling problem, ARMMS searches its memory for solutions. If no solution is available, ARMMS falls back on an analogical problem solving approach in which similar experience can be recalled, and solutions to new, but similar, problems can be constructed. If no similar experience exists, ARMMS intelligently selects an appropriate algorithmic model from its model library, based on the input parameters and problem type, to solve the given problem. By combining experts' knowledge, analogical problem-solving approaches, and algorithmic methods, ARMMS provides an efficient problem-solving approach for vehicle scheduling and routing. ARMMS is also a feasible base for the development of intelligent model management systems.     

Scheduling healthcare services in a home healthcare system

We consider a scheduling problem in a home healthcare system in which nurses visit patients regularly for relatively minor healthcare services. Intervals between the visits may differ for different patients. On each day in the planning horizon, a nurse must visit the patients assigned to her/him on that day, and then return to the hospital. For the problem of determining the visiting schedule with the objective of minimizing total travel time of the nurse over the planning horizon, we develop a two-phase heuristic algorithm. To evaluate performance of the proposed algorithm, a series of computational tests is performed on a number of randomly generated problem instances and a real instance. Results of the tests show that the heuristic algorithm gives near optimal solutions for problems of practical sizes in a reasonable time.     

On maintenance scheduling of production units

A typical maintenance scheduling problem is presented as a large-scale mixed integer nonlinear programming case. Several relaxations of the conditions of variables and constraints are discussed. The optimal solution of the models based on these relaxations is viewed as the lower bound of the optimal solution in the original problem. A combined implicit enumeration and branch-and-bound algorithm is used. Typical dimension of the problems for which computational experience is reported is 25 production units in the system. 19 of these are to be maintained and a planning horizon of 52 weeks with 5 types of hours per week. The corresponding dimensions of the model are about 5700 constraints, 700 binary variables and 6500 nonlinear separable variables.     

A Comparative Study of Multiple-Objective Metaheuristics on the Bi-Objective Set Covering Problem and the Pareto Memetic Algorithm

Many organizations face employee scheduling problems under conditions of variable demand for service over the course of an operating day and across a planning horizon. These organizations are concerned with the tour scheduling problem that involves assigning shifts and break times to the work days of employees and allocating days off to individual work schedules. Nowadays, organizations try to adopt various scheduling flexibility alternatives to meet the fluctuating service demand. On the other hand, they have also realized that providing employee productivity and satisfaction is as much important as meeting the service demand. Up to date, tour scheduling solution approaches have neglected considering employee preferences and tried to develop work schedules for employees in a subsequent step. This paper presents a goal programming model that implicitly represents scheduling flexibility and also incorporates information about the preferred working patterns of employees. After solving the proposed model, a work schedule will be generated for each employee without requiring a further step for the assignment of shifts, break times, and work days to employees. The model is capable of handling multiple scheduling objectives, and it can produce optimal solutions in very short computing times.     

Integrating restoration and scheduling decisions for disrupted interdependent infrastructure systems

We consider the problem faced by managers of critical civil interdependent infrastructure systems of restoring essential public services after a non-routine event causes disruptions to these services. In order to restore the services, we must determine the set of components (or tasks) that will be temporarily installed or repaired, assign these tasks to work groups, and then determine the schedule of each work group to complete the tasks assigned to it. These restoration planning and scheduling decisions are often undertaken in an independent, sequential manner. We provide mathematical models and optimization algorithms that integrate the restoration and planning decisions and specifically account for the interdependencies between the infrastructure systems. The objective function of this problem provides a measure of how well the services are being restored over the horizon of the restoration plan, rather than just focusing on the performance of the systems after all restoration efforts are complete. We test our methods on realistic data representing infrastructure systems in New York City. Our computational results demonstrate that we can provide integrated restoration and scheduling plans of high quality with limited computational resources. We also discuss the benefits of integrating the restoration and scheduling decisions.     

Planning horizons for multi-item hierarchical production scheduling problems: A heuristic search procedure

A proper planning horizon is important to the effectiveness of planning results. However, there is no planning horizon study dealing with multi-item, multi-level production planning problems which are often encountered in reality. In this study, we develop a direct search procedure for finding planning horizons for a multi-item hierarchical production planning process which consists of an aggregate planning problem and a master production scheduling problem. Experimental results show that the search heuristic is quite efficient in finding planning horizons for both aggregate planning problem and the master scheduling problem. The results also show that the master schedule planning horizons need not be longer than the aggregate planning horizons.     

Introducing cost-plus-loss analysis into a hierarchical forestry planning environment

Cost-plus-loss analysis of data for forestry planning has often been carried out for highly simplified planning situations. In this study, we suggest an advance in the cost-plus-loss methodology that aims to capture the hierarchical structure and iterative nature of planning by the large forest owner. The simulation system that is developed to simulate the planning process of the forest owner includes the tactical and operational levels of a continuous planning process. The system is characterized by annual re-planning of the tactical plan with a planning horizon of ten year and with the option to reassess data for selected stands before operational planning. Operational planning is done with a planning horizon of two years and the first year of the plan is considered to have been executed before moving the planning process one year forward. The annual cycle is repeated 10 times, simulating decisions made over a ten-year time horizon. The optimizing planning models of the system consider wood flow requirements, available harvest resources, seasonal variation of ground conditions and spatiality. The data used are evaluated according to standard procedures in cost-plus-loss analysis. Results from a test case indicate high decision losses when planning at both levels is based on the type of data prevalent in the stand databases of Swedish companies. The losses can be reduced substantially if higher-quality data are introduced before operational planning. In summary, the results indicate that the method makes it possible to analyze where in the planning process one needs better data and their value.     

Finding the shortest path with honey-bee mating optimization algorithm in project management problems with constrained/unconstrained resources

Effective project management requires the development of a realistic plan and a clear communication of the plan from the beginning to the end of the project. The critical path method (CPM) of scheduling is the fundamental tool used to develop and interconnect project plans. Ensuring the integrity and transparency of those schedules is paramount for project success. The complex and discrete nature of the solution domain for such problems causes failing of traditional and gradient-based methods in finding the optimal or even feasible solution in some cases. The difficulties encountered in scheduling construction projects with resource constraints are highlighted by means of a simplified bridge construction problem and a basic masonry construction problem. The honey-bee mating optimization (HBMO) algorithm has been previously adopted to solve mathematical and engineering problems and has proven to be efficient for searching optimal solutions in large-problem domains. This paper presents the HBMO algorithm for scheduling projects with both constrained and unconstrained resources. Results show that the HBMO algorithm is applicable to projects with or without resource constraints. Furthermore, results obtained are promising and compare well with those of well-known heuristic approaches and gradient-based methods.