Heuristics, Metaheuristics and Approximate Methods in Planning and Scheduling

Spatial scheduling problems involve a set of jobs which have spatial dimensions in addition to traditional scheduling considerations such as due dates or processing times. In these problems processing space is a limited resource, and the scheduling decisions must determine both when and where the each job will be processed as well as each job’s layout orientation. Spatial scheduling problems find many real-world applications in industries such as shipbuilding and aircraft assembly, where there is limited working space available and tasks utilize significant amounts of spatial resources in their completion. In this chapter we discuss spatial scheduling and present several heuristic and metaheuristic algorithms for this problem class.

The use of production planning algorithms on a rolling horizon basis is very common in practice. However, this leads to frequent changes in planned quantities for future periods which may adversely impact support activities such as material preparation, staffing, and setup planning. In this chapter we examine two widely used approaches for this problem, the use of change costs to penalize changes in planned quantities and freezing of the plan by prohibiting any changes in some number of periods in the near future. We use a linear programming model of a single-product single-stage system to develop insights into the conditions when the two approaches are equivalent. Specifically, we derive lower bounds on the values of the change costs which will ensure freezing of the plan in a given planning epoch, and present numerical results to illustrate our findings.

In this chapter, we address the problem of optimally routing and sequencing a set of jobs over a network of flexible machines for the objective of minimizing the sum of completion times and the cost incurred, assuming stochastic job processing times. This problem is of particular interest for the production control in high investment, low volume manufacturing environments, such as pilot-fabrication of microelectromechanical systems (MEMS) devices. We model this problem as a two-stage stochastic program with recourse, where the first-stage decision variables are binary and the second-stage variables are continuous. This basic formulation lacks relatively complete recourse due to infeasibilities that are caused by the presence of re-entrant flows in the processing routes, and also because of potential deadlocks that result from the first-stage routing and sequencing decisions. We use the expected processing times of operations to enhance the formulation of the first-stage problem, resulting in good linear programming bounds and inducing feasibility for the second-stage problem. In addition, we develop valid inequalities for the first-stage problem to further tighten its formulation. Experimental results are presented to demonstrate the effectiveness of using these strategies within a decomposition algorithm (the L-shaped method) to solve the underlying stochastic program. In addition, we present heuristic methods to handle large-sized instances of this problem and provide related computational results.

This chapter presents a metaheuristic named Meta-Heuristic for Randomized Priority Search (Meta-RaPS), which has been applied to different problems in literature. It mainly explains the overall framework by using an example so the reader can understand how the meta-heuristic works. We at the end identify some future opportunities for research.

Intensification and diversification in metaheuristics are two main strategies to enhance the search process and solution quality. In Meta-RaPS (Metaheuristic for Randomized Priority Search), a recent memoryless metaheuristic, intensification and diversification strategies are controlled only by the level of randomness specified by its parameters. We introduce in this paper a Path Relinking (PR) learning algorithm and integrate it into Meta-RaPS to intelligently enhance its intensification capability by learning “good” attributes of the best solutions. To evaluate its performance, the proposed Meta-RaPS PR is tested on the 0-1 Multidimensional Knapsack Problem (MKP). The results show that applying PR as an intensification strategy in Meta-RaPS is very effective as it outperformed other approaches used in the literature with this problem. The PR approach also transformed the memoryless nature of Meta-RaPS into an “intelligent” algorithm.

This chapter discusses the capability and effectiveness of a Meta-heuristic for Randomized Priority Search to solve multi-objective problems. The multi-objective problem of unrelated parallel machine scheduling is considered in the chapter. The two objectives to minimize are total weighted tardiness and total weighted completion time. An existing construction rule in the literature named Apparent Tardiness Cost-bi heuristic is used as the basis for the meta-heuristic construction phase to generate non-dominated solutions. The computational results obtained are promising when results of the meta-heuristic approach proposed are compared with those of the original construction rule. This chapter illustrates that the meta-heuristic approach proposed is effective and flexible enough to generate Pareto-frontiers in order to solve multi-objective scheduling problems by modifying a simple existing heuristic found in the literature.

This chapter addresses the state-of-the-art heuristic and meta-heuristic approaches for solving aircraft runway scheduling problem under variety of settings. Runway scheduling has been one of the emerging challenges in air traffic control as the congestion figures continue to rise. From a modeling point of view, mixed-integer programming formulations for single and multiple dependent and independent runways are presented. A set partitioning reformulation of the problem is demonstrated which suggests development of a column generation scheme. From a solution methodology viewpoint, generic heuristic algorithms, optimization-based approaches, and a dynamic programming scheme within the column generation algorithm are presented. Common meta-heuristic approaches that model variant problem settings under static and dynamic environments are discussed.

Runways are typically identified as the primary bottleneck of the airport operations system that causes delays. Hence, operational efficiency of runways constitutes a critical factor for the overall air transportation system. Multiple Runway Aircraft Scheduling Problem involves assigning both landing and taking-off aircraft to runways, sequencing them on each runway and assigning each aircraft a landing or take-off time while considering predetermined time windows for each aircraft to land or take-off. Also, sequence-dependent separation times between each aircraft pair in the sequence need to be taken into account in order to avoid wake vortex (turbulence) effects which can pose a hazard caused by preceding aircraft. Several variations of this combinatorial optimization problem are researched extensively in the past decades and a wide variety of algorithms have been proposed for small-scale problems. However, from a practical point of view large-scale real-life problems require fast response times and remain challenging computationally. This chapter aims to present a Tabu Search (TS) algorithm for the static (offline) case of the problem, where all information of aircraft is known in advance. Also, computational results for the proposed algorithm are presented for a number of benchmark instances obtained from literature.

We consider a scheduling problem for parallel identical batch processing machines. A batch is a set of jobs that can be processed at the same time on a single machine. The jobs belong to incompatible job families. Only jobs of the same family can be batched together. We are interested in minimizing the total weighted tardiness (TWT) of the jobs. Problems of this type arise, for instance, in semiconductor manufacturing. Other known occurrence of batch processing machines can be found in gear manufacturing. We describe a genetic algorithm (GA), an ant colony optimization (ACO) approach, and a large neighborhood search (LNS) approach for this scheduling problem. The performance of the three metaheuristic approaches is compared based on randomly generated problem instances. The LNS scheme outperforms the two other metaheuristics and is comparable with a variable neighborhood search (VNS) approach, the best performing heuristic for this scheduling problem from the literature.

In this research, a new metaheuristic called Worm Optimization (WO) is proposed, based on the foraging behaviors of Caenorhabditis elegans (Worms). In particular, the algorithm will mimic the behaviors of worms including finding food, avoiding toxins, interchanging between solitary and social foraging styles, alternating between food exploiting and seeking, and entering a stasis stage. WO effectiveness is illustrated on the traveling salesman problem (TSP), a known NP-hard problem, and compared to well-known naturally inspired algorithms using existing TSP data. The computational results reflected the superiority of WO in all tested problems. Furthermore, this superiority improved as problem sizes increased, and WO attained the global optimal solution in all tested problems within a reasonable computational time.

Planning and scheduling play a very important role in health care. Effective scheduling optimizes the utilization of scarce resources such as operating rooms (ORs), devices in hospitals, and surgeons. Therefore, operations research/operations management techniques have been frequently used in health care systems management. In this chapter, we examine the surgical scheduling problem over multiple operating rooms. In order to find an optimal solution to surgical scheduling problem, mixed-integer programming (MIP) formulation of the surgical scheduling problem is presented. The model includes constraints for several operational rules and requirements found in most hospitals, and specifically minimizes the total weighted start time as a performance measure (or objective function). Since the problem is known to be an NP-hard in most of its forms, heuristic algorithms (i.e., greedy heuristics and a metaheuristic) are also introduced to find near-optimal solutions efficiently.

This chapter discusses a production planning method known as “product wheels.” We define “product wheels,” discuss how they are used, and show the value the technique provides to production operations. We look at the importance of product families in planning production, particularly where set-up costs and time are critical. We examine the question of product sequencing—and why that aspect of manufacturing planning is seldom as difficult and data intensive as the mathematics (e.g., traveling salesman problem) might imply. The chapter analyzes how variants of Economic Order Quantity (“EOQ”) and “EOQ with Joint Replenishment” [E.A. Silver heuristic (1976)] can be used (balancing costs of cycle stock inventory versus transitions) to get early results that lead us towards the formulation of a cost-effective wheel. We also look at the problem of balancing wheels for capacity feasibility when product campaigns cycle at different frequencies.