This paper proposes a new evolutionary partition based method to tackle complex combinatorial optimization problems, such as a class of scheduling problems with hard Q-time constraints. The proposed method creatively integrates prune mechanism and evolutionary theory into the Nested Partition scheme. Theoretical results reveals that this method converges with probability one to the optimal solution for any given combinatorial optimization problem with finite feasible solutions. The study also presents a hybrid variant of this method, incorporating a partheno-genetic algorithm, thereby demonstrating the flexibility and robustness of the proposed method. Through numerical experiments, the robust capacity and efficiency of the proposed methods compared with the Branch and Bound method, the Nested Partition method, and Genetic Algorithms are highlighted.Note to Practitioners—This paper is motivated by a complex large-scale scheduling problem with hard Q-Time constraints prevalent in various industries. Existing methods either fail to meet these hard constraints or satisfy them at the expense of a large makespan. This paper presents a novel evolutionary partition based method with solid mathematical proofs ensuring its capability of problem solving. Numerical results show that our method outperforms existing methods by providing superior quality solutions in a shorter computational time while ensuring that the hard Q-times are met. The effectiveness, efficiency, and flexibility make this method an attractive approach for dealing with practical scheduling problems.

Production scheduling and machine maintenance are two inseparable operational issues in multistage production systems. Previous studies attempted to deal with this issue by simplifying this problem due to the degradation uncertainties of the machines, ignoring the substantial interactions between these two tasks and leading to less efficiency of the entire production system. In this study, we fill the gap and formulate the joint optimization problem with more emphasis on the interaction between job scheduling and maintenance for a series-parallel multistage production system. Specifically, a mixed-effect degradation model is proposed to leverage the underlying interaction between job scheduling and machine maintenance. To efficiently solve this joint problem, several properties from this formulation have been derived. A two-phase method considering condition-based information, with a proactive algorithm for local intensification and a condition-based workload reallocation strategy & maintenance strategy, is then developed to address the uncertainties from the machine degradation status. A numerical study is finally borrowed to demonstrate the higher production efficiency achieved by applying the proposed method, compared with other benchmarks.Note to Practitioners—This study is motivated by a practical scenario where both job allocation and maintenance need to be determined simultaneously in the multistage production system by the operators to achieve time and cost efficiency. We focus on developing a new scheme that job scheduling and machine maintenance are able to be conducted simultaneously. Two issues are noteworthy to better implement this scheme. First, for characterizing the interaction between scheduling and maintenance, the data collected in real-time can provide a sufficient basis for the degradation path, and the production parameters can be acquired from real practice. Second, this scheme can be offered to help decision-making by a two-phase solution framework given the condition-based information during the production process. Specifically, an appropriate job allocation planning can be obtained offline in the first phase of the proposed two-phase solution framework under a limited computing resource. Meanwhile, a condition-based adjustment strategy in the second phase can update the solution based on the in-situ condition information collected from the data platform to achieve higher production efficiency.

The parallel machine scheduling problem has been a popular topic for many years due to its theoretical and practical importance. This paper addresses the robust makespan optimization problem on unrelated parallel machine scheduling with sequence-dependent setup times, where the processing times are uncertain, and the only knowledge is the time intervals they take values from. We propose a robust optimization model with the min-max regret criterion to formulate this problem. To solve this problem, we prove that the worst-case scenario with the maximum regret for a given solution belongs to a finite set of extreme scenarios. Based on this theoretical analysis, a procedure to obtain the maximum regret is proposed and an enhanced regret evaluation method (ERE) is designed to accelerate this process, which is of great significance to improve the efficiency of the algorithm. A multi-start decomposition-based heuristic algorithm (MDH) based on the analysis of properties is proposed to solve this problem. Computational experiments are conducted to justify the performance and robustness of these methods. Note to Practitioners—Various uncertainties may occur in the production process, which brings great challenges to production and operations management. A robust production schedule is of great significance for factories to make full use of production capacity and deal with production abnormalities. This study is motivated by an R&D and assembly task scheduling problem encountered in a high-end equipment manufacturing factory in which the processing time of each job is uncertain, and its distribution is also unknown due to limited information. In this study, with the consideration of sequence-dependent setup time and uncertain job-processing time, we view the labor groups with different skill levels as unrelated parallel machines and build a robust (min-max regret) scheduling model to formulate this problem so as to reduce the production makespan. An enhanced regret evaluation method is developed to improve the evaluation efficiency for a given solution, and a multi-start decomposition-based heuristic algorithm is proposed to solve this problem. This study can be applied in practice to release schedulers from burdensome work and provide high-quality robust schedules for this complicated production environment.

Monte Carlo simulation is a commonly used tool for evaluating the performance of complex stochastic systems. In practice, simulation can be expensive, especially when comparing a large number of alternatives, thus motivating the need to intelligently allocate simulation replications. Given a finite set of alternatives whose means are estimated via simulation, we consider the problem of determining the subset of alternatives that have means smaller than a fixed threshold. A dynamic sampling procedure that possesses not only asymptotic optimality, but also desirable finite-sample properties is proposed. Theoretical results show that there is a significant difference between finite-sample optimality and asymptotic optimality. Numerical experiments substantiate the effectiveness of the new method. Summary of Contribution: Simulation is an important tool to estimate the performance of complex stochastic systems. We consider a feasibility determination problem of identifying all those among a finite set of alternatives with mean smaller than a given threshold, in which the means are unknown but can be estimated by sampling replications via stochastic simulation. This problem appears widely in many applications, including call center design and hospital resource allocation. Our work considers how to intelligently allocate simulation replications to different alternatives for efficiently finding the feasible alternatives. Previous work focuses on the asymptotic properties of the sampling allocation procedures, whereas our contribution lies in developing a finite-budget allocation rule that possesses both asymptotic optimality and desirable finite-budget properties.

Electron beam inspection (EBI) with high resolution is a promising technique to improve the defect inspection on the surface of patterned wafer. However, high resolution usually means long inspection time, which results in the low throughput and limitation of EBI applied in practice. This study aims to optimize the inspection time of EBI by reducing the total number of inspection regions without loss of the accuracy. We first refine this defect inspection optimization problem as a partial congruent square cover problem. Then, we propose two novel mixed-integer linear programming models for this problem. To deal with the large-scale problems, an approximation algorithm is developed to obtain the high-quality solutions. This approximation algorithm efficiently utilizes the linear programming (LP) rounding technique and greedy strategy based on the proposed model. Compared with the existing algorithms in the literature, numerical results show the superiority of the proposed model and algorithm.Note to Practitioners—Defect inspection is a key process in wafer fabrication for identifying and inspecting the patterning defects generated during the complicated fabrication processes. Electron beam inspection (EBI) takes place of optical inspection gradually as the design rules keep shrinking and the circuits are more susceptible to nanoscale killer defects. Low throughput is the main drawback of EBI and the improvements on throughput have far-reaching significance on the high volume manufacturing of semiconductor products. This study aims to reduce the number of inspection regions to improve the total inspection time in the EBI process. Considering that the inspection time for each inspection region is constant, less inspection regions means less total inspection time. However, the positions of inspection regions are arbitrary across the continuous planar space, putting pressure on modeling and solving the problem. A preprocessing algorithm is designed to discover a limited number of candidate positions of inspection regions without loss of optimality, which greatly simplifies the problem. For dealing with large-scale instances, an approximation algorithm combining linear programming (LP)-rounding technique and greedy strategy is designed to get near optimal solutions. Since the number of inspection regions is one key factor determining the total inspection time, the proposed optimization methods have a potential to be applicable to enhance the efficiency of advanced EBI platforms, such as ASML HMI eP series.

This article investigates a hybrid flow shop scheduling problem that consists of a batch processor in the upstream and a discrete processor in the downstream. Limited waiting time between the batch processor and discrete processor is taken into consideration. Such a scheduling problem is commonly seen as bottlenecks in the production of precision parts, back-end process of semiconductor products, and glass and steel industries. A mixed-integer linear programming model is presented to minimize the makespan. Considering the complexity of this problem and the imperative requirement in real-time optimization, we first develop a constructive heuristic together with the worst case analysis by exploiting the key decision structure of the problem. Based on the decision structure, we then develop a learning-based scheduling approach via customized genetic programming to automatically generate effective heuristics for this problem. Lower bounds are also developed to provide a measurement for the performance of proposed algorithms. Numerical results show that our proposed algorithms outperform the existing metaheuristics and are capable of providing high-quality solutions using less computational time. Note to Practitioners-The production system consisting of a batch processor in the upstream and a discrete processor in the downstream is common in practice. The batch processor first handles a group of jobs simultaneously. Then, the jobs are released to a buffer to wait for the process on the discrete processor one by one. However, the waiting time of the jobs in the buffer is often required to be limited according to the production requirements. For example, after being heated in the heat-treatment oven, the aerospace precision parts have to be processed on the machining equipment in limited waiting time to improve the processability in subsequent manufacturing. The semiconductor chips have to be packed in limited waiting time after baking to avoid getting wet. The incongruous production modes between the batch processor and discrete processor, together with the limited waiting time constraint, make such operations always the bottleneck in manufacturing. Efficient heuristics, providing high-quality solutions with low time complexity, are much preferred in practice for most of the complicated scheduling problems, such as the scenarios described earlier. However, the designing process of an effective heuristic is tedious, and the heuristic is usually deeply customized for a certain production scenario. Genetic programming (GP) provides an inspiring approach to automatically generate sophisticated heuristics for complicated scheduling problems through evolutionary learning processes. By customizing a GP-based approach, the designing process of heuristics is automated, and some undetectable knowledge relations can be obtained to enhance the quality of heuristics. Such an approach facilitates to obtain more sophisticated schedules by analyzing valuable knowledge for smart manufacturing. The superiority of the heuristic learned by GP is shown in the computational experiment, and it has great potential to be applied to the practical scheduling.

This article addresses a real-world tactical production planning problem in which a series of real-world constraints need to be considered, such as no backorder, products with multilevel bills of material (BOMs), and lot streaming production. Under the premise of no backorder, the objective of this plan is to make the workload as balanced as possible throughout the planning horizon. An integer quadratic programming model is first proposed to formulate this problem. Then, based on the analysis of the optimal solution for a common BOM structure, this problem is reformulated to a simplified problem where only one item in BOM needs to be considered. Some optimality properties are further derived to help solve this problem. An enhanced variable neighborhood search algorithm is developed to solve this problem, and a lower bound is put forward to measure the performance of the algorithm. Experimental results show that this algorithm can obtain high-quality solutions in a short time.

Many problems in automation and manufacturing are most suitable to be modeled as simulation optimization problems. Solving these problems typically involves two efforts: one is to explore the solution space, and the other is to exploit the performance values of the sampled solutions. When the amount of computing budget is limited, we need to know how to balance these two efforts in order to obtain the best result. In this study, we derive two measures to quantify the marginal contribution of exploring the search space and exploiting the performance values. A sequential budget allocation framework is designed by keeping the two measures approximately the same at each iteration. Numerical experiments on both continuous and discrete simulation optimization problems demonstrate that our new approach can significantly enhance the computing efficiency.

In this study, the customer order scheduling problem is investigated to minimize total weighted completion time. A quadratic formulation is proposed to address this problem. This formulation is converted into an equivalent mixed-integer linear programming model by applying the linearization technique and the special structure of the problem. The problem size that can be solved to optimality is then investigated and reported based on the final linearized formulation. Furthermore, a hybrid nested partitions algorithm is developed to solve large-scale problems. Numerical results illustrate the advantages of the proposed model and demonstrate that the proposed algorithm can obtain high-quality solutions within a reasonable computational time.

In this paper, we study the radiation treatment planning optimization for Volumetric-Modulated Arc Therapy (VMAT). A nonlinear mixed integer programming model is formulated, then the linearization technique is used, and the resulting mixed integer programming model is solved by a heuristic approach based on the Nested-Partitions framework. The approach partitions the feasible region iteratively and constructs a feasible solution by solving the LP relaxation of the original problem. We design two partition strategies: partition by column and expansion from center of aperture. Numerical results with clinical cases show the efficiency of the proposed model and algorithm.

Partition-based random search (PRS) provides a class of effective algorithms for global optimization. In each iteration of a PRS algorithm, the solution space is partitioned into subsets which are randomly sampled and evaluated. One subset is then determined to be the promising subset for further partitioning. In this paper, we propose the problem of allocating samples to each subset so that the samples are utilized most efficiently. Two types of sample allocation problems are discussed, with objectives of maximizing the probability of correctly selecting the promising subset$(P\{CSPS\})$given a sample budget and minimizing the required sample size to achieve a satisfied level of$P\{CSPS\}$, respectively. An extreme value-based prospectiveness criterion is introduced and an asymptotically optimal solution to the two types of sample allocation problems is developed. The resulting optimal sample allocation strategy (OSAS) is an effective procedure for the existing PRS algorithms by intelligently utilizing the limited computing resources. Numerical tests confirm that OSAS is capable of increasing the$P\{CSPS\}$in each iteration and subsequently improving the performance of PRS algorithms.

Metaheuristics are an important branch of optimization algorithms that attract lots of research and application efforts. In this paper, the research of predicting solution value for Nested Partitions (NP) is proposed, which is a newly developed metaheuristic algorithm for solving large-scale optimization problems. The lower bound embedded prediction procedures are developed to predict the future performance of NP based on the solution values obtained at early iterations. The prediction procedures are used in an enhanced NP algorithm to select a proper algorithm setting for NP at early stage, which saves a lot of computational resource for large-scale problems. The computational tests show the accuracy and effectiveness of the proposed algorithm. These prediction procedures can be also applied to some other metaheuristics.

Timely supply of vital materials to disaster hit areas plays a critical role in emergency relief. The problem involves warehouse selection, fleet routing, and scheduling so as to meet demand in the strict time window. The problem is NP-hard, in general, and extremely difficult to solve. The congestion caused by heavy traffic further aggravates the problem. To obtain a scalable solution, a new method based on successive subproblem solving in Lagrangian Relaxation (LR) framework is developed. The route capacity and location selection constraints are relaxed by Lagrange multipliers, and the problem is converted into a two-level optimization problem. The subproblems at the lower level are solved successively in dual iterations with convergence assurance so that the indecomposable location constraints can be incorporated. A systematic method is developed to obtain a feasible solution by adding the once relaxed constraints back into the dual problem successively in feasibility iterations. Convergence proof of the new method and its properties are presented. Numerical results show that the new method is effective and efficient, and can be applied to large-scale problems.

In this paper, dynamic behavior is compared for two methods of local work in progress (WIP) regulation in autonomous work systems in production networks. In one method, work systems do not share information regarding the expected physical flow of orders between them; in the other, order-flow information is shared to compensate for the variable dynamic effects of physical order-flow coupling. In both methods, the work systems adjust production rate with the objective of maintaining a desired amount of local WIP. A linear discrete-time dynamic model of the flow of orders between work systems is used, which promotes identification of fundamental properties such as characteristic times and damping. The results demonstrate the need for order-flow information sharing in establishing desired network dynamic behavior. Examples are used to illustrate behavior in the general case of omnidirectional order flows and the special case of unidirectional order flows.

In this paper, we consider the capacitated multi-item lot sizing problem with setup times. The problem is to schedule J different items over a horizon of T periods with the objective to minimize the sum of setup cost and inventory holding cost. To achieve feasible high-quality solutions, we propose a new solution approach which hybrids Nested Partitions and Mathematical Programming (HNP-MP). Nested Partitions is a partitioning and sampling based heuristic method with a global perspective on the problem. In the proposed new method the Mathematical Programming method is implemented to calculate the promising index and to provide a good guidance on partitioning in the Nested Partitions framework. A time-oriented decomposition heuristic method, Relax-and-Fix, is also implemented to obtain good promising regions and speed up the computational process. Computational results based on benchmark test problems show that the approach is computationally tractable and is able to obtain good results. The approach outperforms other state-of-the-art approaches found in the literature.

Purpose: To predict organ-at-risk (OAR) complications as a function of dose-volume (DV) constraint settings without explicit plan computation in a multi-plan IMRT framework. Methods and Materials: A large number of plans were generated by varying the DV constraints (input features) on the OARs (multi-plan framework), and the OAR complications in the plans (plan properties) were modeled as a function of the imposed DV constraint settings, which were used as input to machine learning (ML) algorithms. These ML approaches were used to model two OAR complications following head-and-neck and whole pelvis/prostate intensity-modulated radiation therapy, xerostomia and grade 2 rectal bleeding. Two-fold cross-validation was used for model verification and mean errors were reported. Results: In the head and neck case, the mean absolute prediction error of the saliva flow rate normalized to the pre-treatment saliva flow rate was 0.42% with a 95% confidence interval of [0.41%, 0.43%]. In the whole pelvis/prostate case, an average prediction accuracy of 97.04% with a 95% confidence interval of [96.67%, 97.41%] was achieved for grade 2 rectal bleeding complications. Conclusion: ML can be used for predicting OAR complications during treatment planning allowing for alternative DV constraint settings to be assessed within the planning framework.

We provide a framework for integrating two stages of radiation treatment planning (RTP): beam-angle selection (BAS) and dose optimization (DO). The framework is applied to both classical three-dimensional conformal radiotherapy and advanced intensity-modulated radiation therapy. Automated BAS and improved dose distribution are achieved within the framework. A metaheuristic approach, nested partitions, is applied. Alternative BAS and DO algorithms or commercial RTP software and clinical experience can be embedded within the framework to provide new methods for warm starts and evaluations of the quality of beam-angle set samples. Computational efficiency is achieved by utilizing high-throughput computing via the Condor system. Computational results show that our framework has led to a significant improvement in terms of solution quality and delivery time compared with current clinical practice.

Dynamic programming, branch-and-bound, and constraint programming are the standard solution principles for finding optimal solutions to machine scheduling problems. We propose a new hybrid optimization framework that integrates all three methodologies. The hybrid framework leads to powerful solution procedures. We demonstrate our approach through the optimal solution of the single-machine total weighted completion time scheduling problem subject to release dates, which is known to be strongly NP-hard. Extensive computational experiments indicate that new hybrid algorithms use orders of magnitude less storage than dynamic programming, and yet can still reap the full benefit of the dynamic programming property inherent to the problem. We are able to solve to optimality all 1900 instances with up to 200 jobs. This more than doubles the size of problems that can be solved optimally by the previous best algorithm running on the latest computing hardware.

Large-scale discrete optimization problems are difficult to solve, especially when different kinds of real constraints are considered. Conventionally, standard mathematical programming is a general approach for discrete optimization, but may suffer from the unacceptable long solution time in applications. On the other hand, some heuristics/metaheuristics methods are more powerful in finding approximate solutions efficiently, but mostly are problem and constraint dependent. In this paper, we develop a new hybrid nested partitions and mathematical programming approach, which creates compliance between mathematical programming and the heuristics/metaheuristics methods. Potentially applicable to many different types of problems, the hybrid approach can provide approximate solutions efficiently, and in the meantime can easily handle different kinds of constraints. The applications of the hybrid approach to the local pickup and delivery problem (LPDP) and the discrete facility location problem (DFLP) are presented in this paper.

This paper addresses the general single-machine earliness-tardiness problem with distinct release dates, due dates, and unit costs. The aim of this research is to obtain an exact nonpreemptive solution in which machine idle time is allowed. In a hybrid approach, we formulate and then solve the problem using dynamic programming (DP), while incorporating techniques from branch-and-bound (BB). This approach (DP-BB) has been proven to be effective in solving certain types of scheduling problems. We further propose a new adaptation of the approach to a general problem with a nonregular objective function. To address some shortcomings of DP-BB, we also apply a BB approach in which partial dynamic programming dominance (BB-PDP) is exploited. Computational experiments were conducted with randomly generated test instances in order to evaluate the effectiveness of the two approaches. The results clearly showed that our new approaches can solve all the instances with up to 40 jobs and most of the instances with 50 jobs, which outperforms those frequently used approaches in scheduling research.

We study a single-machine sequencing problem with both release dates and deadlines to minimize the total weighted completion time. We propose a branch-and-bound algorithm for this problem. The algorithm exploits an effective lower bound and a dynamic programming dominance technique. As a byproduct of the lower bound, we have developed a new algorithm for the generalized isotonic regression problem; the algorithm can also be used as an O(nlogn)-time timetabling routine in earliness-tardiness scheduling. Extensive computational experiments indicate that the proposed branch-and-bound algorithm competes favorably with a dynamic programming procedure. Note to Practitioners-Real-life production systems usually involve multiple machines and resources. The configurations of such systems may be complex and subject to change over time. Therefore, model-based solution approaches, which aim to solve scheduling problems for specific configurations, will inevitably run into difficulties. By contrast, decomposition methods are much more expressive and extensible. The single-machine problem and its solution procedure studied in this paper will prove useful to a decomposition method that decomposes multiple-machine, multiple-resource scheduling problems into a number of single-machine problems. The total weighted completion time objective is relevant to production environments where inventory levels and manufacturing cycle times are key concerns. Future research can be pursued along two directions. First, it seems to be necessary to further generalize the problem to consider also negative job weights. Second, the solution procedure developed here is ready to be incorporated into a machine-oriented decomposition method such as the shifting bottleneck procedure.

We present an efficient search method for job-shop scheduling problems. Our technique is based on an innovative way of relaxing and subsequently reimposing the capacity constraints on some critical operations. We integrate this technique into a fast tabu search algorithm. Our computational results on benchmark problems show that this approach is very effective. Upper bounds for 11 well-known test problems are thus improved. Through the work presented We hope to move a step closer to the ultimate vision of an automated system for generating optimal or near-optimal production schedules. The peripheral conditions for such a system are ripe with the increasingly widespread adoption of enterprise information systems and plant floor tracking systems based on bar code or wireless technologies. One of the remaining obstacles, however, is the fact that scheduling problems arising from many production environments, including job-shops, are extremely difficult to solve. Motivated by recent success of local search methods in solving the job-shop scheduling problem, we propose a new diversification technique based on relaxing and subsequently reimposing the capacity constraints on some critical operations. We integrate this technique into a fast tabu search algorithm and are able to demonstrate its effectiveness through extensive computational experiments. In future research, we will consider other diversification techniques that are not restricted to critical operations.