Effective heuristics for the blocking flowshop scheduling problem with makespan minimization

The blocking flowshop scheduling problem with makespan criterion has important applications in a variety of industrial systems. Heuristics that explore specific characteristics of the problem are essential for many practical systems to find good solutions with limited computational effort. This paper first presents two simple constructive heuristics, namely weighted profile fitting (wPF) and PW, based on the profile fitting (PF) approach of McCormick et al. [Sequencing in an assembly line with blocking to minimize cycle time. Operations Research 1989;37:925-36] and the characteristics of the problem. Then, three improved constructive heuristics, called PF-NEH, wPF-NEH, and PW-NEH, are proposed by combining the PF, wPF, and PW with the enumeration procedure of the Nawaz-Enscore-Ham (NEH) heuristic [A heuristic algorithm for the m-machine, n-job flow shop sequencing problem. OMEGA-International Journal of Management Science 1983;11:91-5] in an effective way. Thirdly, three composite heuristics i.e., PF-NEH_LS, wPF-NEH_LS, and PW-NEH_LS, are developed by using the insertion-based local search method to improve the solutions generated by the constructive heuristics. Computational simulations and comparisons are carried out based on the well-known flowshop benchmarks of Taillard [Benchmarks for basic scheduling problems. European Journal of Operation Research 1993;64:278-85] that are considered as blocking flowshop instances. The results show that the presented constructive heuristics perform significantly better than the existing ones, and the proposed composite heuristics further improve the presented constructive heuristics by a considerable margin. In addition, 17 new best-known solutions for Taillard benchmarks with large scale are found by the presented heuristics.     

Entscheidungsunterstützung unter Berücksichtigung der Anforderungen von Entscheidungsträgern am Beispiel der Gestaltung von optionalen Girokonto-Tarifen

Quantitative decision models are used only if managers’ implementation conditions are met. Decision makers want tools that offer a set of good solutions so that they can evaluate different solutions according to various objectives without being forced to make their trade-offs explicit in a functional form. This also allows taking into account strategic aspects that cannot be modeled otherwise. In such situations, heuristics are needed which derive solutions from the structure and not so much from the mathematical properties. We present such a decision support tool for the problem of determining a menu of optional tariffs for checking accounts. The heuristic is based on the idea that for reasonably separable preferences across segments it is the best to offer for each segment the most preferred product. We use latent class choice-based conjoint analysis to estimate customer preferences and develop a customized choice-based conjoint design to take differences in individual demand into account. The proposed heuristic was used to support an actual decision problem for which the profit contribution has been increased substantially without having faced a considerable loss of customers.     

Assembly Line Balancing Using Genetic Algorithms with Heuristic-Generated Initial Populations and Multiple Evaluation Criteria*

We use genetic algorithms (GA) to solve the assembly line balancing (ALB) problem. Inparticular, we show how this technique can be used to generate feasible line balances, improve upon solutions obtained by other heuristics reported in the literature, and utilizeany one or more evaluation criteria that can be expressed in functional form. The procedure is demonstrated with two examples: (1) intimating the improvement of heuristic-generated ALB solutions by including them in the GA initial population, and (2) the possibility of balancing assembly lines with multiple criteria and side constraints. These examples suggest that GA can be a powerful tool in ALB. To investigate the utility of GA on single-criterion problems, an experiment is conducted that compares both the GA approach and conventional heuristics. Results indicate that the GA solutions are significantly improved over the heuristic solutions under the conditions studied. It is also found that the presence of heuristic-generated conventional solutions in the GA initial population leads to statistically preferred results.     

Bi‐Criteria Scheduling of Surgical Services for an Outpatient Procedure Center

Uncertainty in the duration of surgical procedures can cause long patient wait times, poor utilization of resources, and high overtime costs. We compare several heuristics for scheduling an Outpatient Procedure Center. First, a discrete event simulation model is used to evaluate how 12 different sequencing and patient appointment time‐setting heuristics perform with respect to the competing criteria of expected patient waiting time and expected surgical suite overtime for a single day compared with current practice. Second, a bi‐criteria genetic algorithm (GA) is used to determine if better solutions can be obtained for this single day scheduling problem. Third, we investigate the efficacy of the bi‐criteria GA when surgeries are allowed to be moved to other days. We present numerical experiments based on real data from a large health care provider. Our analysis provides insight into the best scheduling heuristics, and the trade‐off between patient and health care provider‐based criteria. Finally, we summarize several important managerial insights based on our findings.     

MINIMIZING TOTAL WEIGHTED COMPLETION TIME ON A SINGLE BATCH PROCESSING MACHINE

We study the problem of scheduling jobs on a single batch processing machine to minimize the total weighted completion time. A batch processing machine is one that can process a number of jobs simultaneously as a batch. The processing time of a batch is given by the processing time of the longest job in the batch. We present a branch and bound algorithm to obtain optimal solutions and develop lower bounds and dominance conditions. We also develop a number of heuristics and evaluate their performance through extensive computational experiments. Results show that two of the heuristics consistently generate high-quality solutions in modest CPU times.     

Assortment optimisation problem: A distribution-free approach

Assortment optimisation is a critical decision that is regularly made by retailers. The decision involves a trade-off between offering a larger assortment of products but smaller inventories of each product and offering a smaller number of varieties with more inventory of each product. We propose a robust, distribution-free formulation of the assortment optimisation problem such that the assortment and inventory levels can be jointly optimised without making specific assumptions on the demand distributions of each product. We take a max-min approach to the problem that provides a guaranteed lower bound to the expected profit when only the mean and variance of the demand distribution are known. We propose and test three heuristic algorithms that provide solutions in O(nlog (n)) time and identify two cases where one of the heuristics is guaranteed to return optimal policies. Through numerical studies, we demonstrate that one of the heuristics performs extremely well, with an average optimality gap of 0.07% when simulated under varying conditions. We perform a sensitivity analysis of product and store demand attributes on the performance of the heuristic. Finally, we extend the problem by including maximum cardinality constraints on the assortment size and perform numerical studies to test the performance of the heuristics.     

Bounding Optimal Expected Revenues for Assortment Optimization under Mixtures of Multinomial Logits

We consider assortment problems under a mixture of multinomial logit models. There is a fixed revenue associated with each product. There are multiple customer types. Customers of different types choose according to different multinomial logit models whose parameters depend on the type of the customer. The goal is to find a set of products to offer so as to maximize the expected revenue obtained over all customer types. This assortment problem under the multinomial logit model with multiple customer types is NP‐complete. Although there are heuristics to find good assortments, it is difficult to verify the optimality gap of the heuristics. In this study, motivated by the difficulty of finding optimal solutions and verifying the optimality gap of heuristics, we develop an approach to construct an upper bound on the optimal expected revenue. Our approach can quickly provide upper bounds and these upper bounds can be quite tight. In our computational experiments, over a large set of randomly generated problem instances, the upper bounds provided by our approach deviate from the optimal expected revenues by 0.15% on average and by less than one percent in the worst case. By using our upper bounds, we are able to verify the optimality gaps of a greedy heuristic accurately, even when optimal solutions are not available.     

Quantitative Comparison of Approximate Solution Sets for Bi‐criteria Optimization Problems*

We present the Integrated Preference Functional (IPF) for comparing the quality of proposed sets of near‐pareto‐optimal solutions to bi‐criteria optimization problems. Evaluating the quality of such solution sets is one of the key issues in developing and comparing heuristics for multiple objective combinatorial optimization problems. The IPF is a set functional that, given a weight density function provided by a decision maker and a discrete set of solutions for a particular problem, assigns a numerical value to that solution set. This value can be used to compare the quality of different sets of solutions, and therefore provides a robust, quantitative approach for comparing different heuristic, a posteriori solution procedures for difficult multiple objective optimization problems. We provide specific examples of decision maker preference functions and illustrate the calculation of the resulting IPF for specific solution sets and a simple family of combined objectives.     

Solution Structure of Some Inverse Combinatorial Optimization Problems

In this paper we consider some inverse combinatorial optimization problems, that is, for a given set of feasible solutions of an optimization problem, we wish to know: under what weight vectors (or capacity vectors) will these feasible solutions become optimal solutions? We analysed shortest path problem, minimum cut problem, minimum spanning tree problem and maximum-weight matching problem, and found that in each of these cases, the solution set of the inverse problem is charaterized by solving another combinatorial optimization problem. The main tool in our approach is Fulkerson's theory of blocking and anti-blocking polyhedra with some necessary revisions.     

Applying statistical tests to empirically compare tabu search parameters for MAX 3-SATISFIABILITY: A case study

The application of stochastic heuristic, like tabu search or simulated annealing, to address hard discrete optimization problems has been an important advance for efficiently obtaining good solutions in a reasonable amount of computing time. A challenge when applying such heuristics is assessing when a particular set of parameter values yields better performance compared to other such sets of parameter values. For example, it can be difficult to determine the optimal mix of memory types to incorporate into tabu search. This in turn prompts users to undertake a trial and error phase to determine the best combination of parameter settings for the problem under study. Moreover, for a given problem instance, one set of heuristic parameter settings may yield a better solution than another set of parameters, for a given initial solution. However, the performance of this heuristic on this instance for a single heuristic execution is not sufficient to assert that the first set of parameter settings will always produce superior results than the second set of parameters, for all initial solutions.     

On the Robust Single Machine Scheduling Problem

The single machine scheduling problem with sum of completion times criterion (SS) can be solved easily by the Shortest Processing Time (SPT) rule. In the case of significant uncertainty of the processing times, a robustness approach is appropriate. In this paper, we show that the robust version of the (SS) problem is NP-complete even for very restricted cases. We present an algorithm for finding optimal solutions for the robust (SS) problem using dynamic programming. We also provide two polynomial time heuristics and demonstrate their effectiveness.     

Integrated Order Scheduling and Packing

We consider an integrated production–distribution scheduling model in a make‐to‐order supply chain consisting of one supplier and one customer. The supplier receives a set of orders from the customer at the beginning of a planning horizon. The supplier needs to process all the orders at a single production line, pack the completed orders to form delivery batches, and deliver the batches to the customer. Each order has a weight, and the total weight of the orders packed in a batch must not exceed the capacity of the delivery batch. Each delivery batch incurs a fixed distribution cost. The problem is to find jointly a schedule for order processing and a way of packing completed orders to form delivery batches such that the total distribution cost (or equivalently, the number of delivery batches) is minimized subject to the constraint that a given customer service level is guaranteed. We consider two customer service constraints—meeting the given deadlines of the orders; or requiring the average delivery lead time of the orders to be within a given threshold. Several problems of the model with each of those constraints are considered. We clarify the complexity of each problem and develop fast heuristics for the NP‐hard problems and analyze their worst‐case performance bounds. Our computational results indicate that all the heuristics are capable of generating near optimal solutions quickly for the respective problems.     

A Strategic,Area-wide Contingency Planning Model for Oil Spill Cleanup Operations with Application Demonstrated to the Galveston Bay Area*

This paper develops a general integer programming model for strategic, area-wide contingency planning of oil spill cleanup operations. Model inputs include the set of risk points and the likely spill scenarios and response requirements for each, the sites of existing storage locations and the inventory of components at each, and potential sites for new storage locations. The model prescribes a minimum total cost plan to either build new storage locations, expand existing ones, or both, to purchase new components and pre-position them, and a contingency plan that determines which response systems should be composed to enable an effective time-phased response for each likely spill scenario. A family of heuristics based on linear programming (LP) is devised to resolve this strategic problem, providing an area-wide contingency plan. The heuristics are evaluated on a set of 10 test problems that involve 1869 general integer variables and 3264 constraints. Computational tests indicate that four heuristics are quite effective, prescribing solutions for each of 10 test cases within 1.41% of optimum and within a few minutes runtime. This study focused on modeling the Galveston Bay Area, and the test problems represent application in that area. A sensitivity analysis is demonstrated by assessing the impacts of component availability and the degradation of cleanup capability over time. Use of the model as a decision support aid by responsible parties, contractors, governmental organizations and others is described.     

Scheduling Methods for Efficient Stamping Operations at an Automotive Company

We consider scheduling issues at Beyçelik, a Turkish automotive stamping company that uses presses to give shape to metal sheets in order to produce auto parts. The problem concerns the minimization of the total completion time of job orders (i.e., makespan) during a planning horizon. This problem may be classified as a combined generalized flowshop and flexible flowshop problem with special characteristics. We show that the Stamping Scheduling Problem is NP‐Hard. We develop an integer programming‐based method to build realistic and usable schedules. Our results show that the proposed method is able to find higher quality schedules (i.e., shorter makespan values) than both the company's current process and a model from the literature. However, the proposed method has a relatively long run time, which is not practical for the company in situations when a (new) schedule is needed quickly (e.g., when there is a machine breakdown or a rush order). To improve the solution time, we develop a second method that is inspired by decomposition. We show that the second method provides higher‐quality solutions—and in most cases optimal solutions—in a shorter time. We compare the performance of all three methods with the company's schedules. The second method finds a solution in minutes compared to Beyçelik's current process, which takes 28 hours. Further, the makespan values of the second method are about 6.1% shorter than the company's schedules. We estimate that the company can save over €187,000 annually by using the second method. We believe that the models and methods developed in this study can be used in similar companies and industries.     

On cutting stock with due dates

Classical stock cutting calls for fulfilling a given demand of parts, minimizing raw material needs. With the production of each part type regarded as a job due within a specific date, a problem arises of scheduling cutting operations. We here propose an exact integer linear programming formulation, and develop primal heuristics, upper bounds and an implicit enumeration scheme. A computational experience carried out for the one-dimensional problem shows that our primal heuristics outperform known ones, and that the formulation has good features for finding exact solutions of non-trivial instances.     

The Effectiveness of Different Representations for Managerial Problem Solving: Comparing Tables and Maps

Geographic Information Systems (GIS) enable decision makers to view tabular data geographically, as maps. This simple yet powerful visual format appears to facilitate problem solving, yet how it does so is not clear, nor do we know the types of problems that benefit from this representation. To begin to understand the contributions of geographic representations over tabular representations, we conducted a three-factor experiment in problem solving. The experiment contained two different representations (map and table), three different geographic relationships (proximity, adjacency, and containment), and three levels of task difficulty (low, medium, and high). We found that maps generally produced faster problem solving than tables, and that problem-solving time increased with task difficulty. Most importantly, for the proximity and adjacency geographic relationships we found that maps kept problem-solving time low, while tables tended to increase time dramatically. However, we found that the number of knowledge states for each task explains performance times quite well and is a useful tool for understanding performance differences and interaction effects. As tasks become more difficult, representing them as maps generally keeps the number of knowledge states small, while for tables, the number of knowledge states increases dramatically. Correspondingly, problem-solving times increase dramatically with tables, but not with maps. In sum, as difficulty increases, maps are more effective for problem-solving tasks. Using maps, the tasks are simplified using visual heuristics that keep problemsolving times and error rates from rising as quickly as they do with tables.     

Parallel machine scheduling subject to auxiliary resource constraints

This paper is motivated by scheduling photolithography machines in semiconductor manufacturing wherein reticle requirements are the auxiliary resource constraints. As the problem is NP hard, two different heuristic solution approaches are developed. The performance of our network-based mathematical model and heuristics are evaluated through an extensive set of problem instances. The best performing heuristic method typically produces solutions that are 1.72% above optimal. If this method is used as the seed solution for a Tabu search-based post processing algorithm, schedules that are 0.78% above the optimal solution, on average, are possible.     

Obtaining Informationally Consistent Decisions When Computing Costs with Limited Information

We demonstrate the need to view in a dynamic context any decision based on limited information. We focus on the use of product costs in selecting the product portfolio. We show how ex post data regarding the actual costs from implementing the decision leads to updating of product cost estimates and potentially trigger a revision of the initial decision. We model this updating process as a discrete dynamical system (DDS). We define a decision as informationally consistent if it is a fixed‐point solution to the DDS. We employ numerical analysis to characterize the existence and properties of such solutions. We find that fixed points are rare, but that simple heuristics find them often and quickly. We demonstrate the usefulness and robustness of our methodology by examining the interaction of limited information with multiple decision rules (heuristics) and problem features (size of product portfolio, profitability of product markets). We discuss implications for research on cost systems.     

Shelf Space Management When Demand Depends on the Inventory Level

Two factors that their influence on the demand has been investigated in many papers are (i) the shelf space allocated to a product and to its complement or supplement products and (ii) the instantaneous inventory level seen by customers. Here we analyze the joint shelf space allocation and inventory decisions for multiple items with demand that depends on both factors. The traditional approach to solve inventory models with a state‐dependent demand rate uses a time domain approach. However, this approach often does not lead to closed‐form expressions for the profit rate with both dependencies. We analyze the problem in the inventory domain via level crossing theory. This approach leads to closed‐form expressions for a large set of demand rate functions exhibiting both dependencies. These closed‐form expressions substantially simplify the search for optimal solutions; thus we use them to solve the joint inventory control and shelf space allocation problem. We consider examples with two products to investigate the significance of capturing both demand dependencies. We show that in some settings it is important to capture both dependencies. We consider two heuristics, each one of them ignores one of the two dependencies. Using these heuristics it seems that ignoring the dependency on the shelf space might be less harmful than ignoring the dependency on the inventory level, which, based on computational results, can lead to profit losses of more than 6%. We demonstrate that retailers should use their operational control, e.g., reorder point, to promote higher demand products.     

A comparison of fixed and dynamic pricing policies in revenue management

We consider the problem of selling a fixed capacity or inventory of items over a finite selling period. Earlier research has shown that using a properly set fixed price during the selling period is asymptotically optimal as the demand potential and capacity grow large and that dynamic pricing has only a secondary effect on revenues. However, additional revenue improvements through dynamic pricing can be important in practice and need to be further explored. We suggest two simple dynamic heuristics that continuously update prices based on remaining inventory and time in the selling period. The first heuristic is based on approximating the optimal expected revenue function and the second heuristic is based on the solution of the deterministic version of the problem. We show through a numerical study that the revenue impact of using these dynamic pricing heuristics rather than fixed pricing may be substantial. In particular, the first heuristic has a consistent and remarkable performance leading to at most 0.2% gap compared to optimal dynamic pricing. We also show that the benefits of these dynamic pricing heuristics persist under a periodic setting. This is especially true for the first heuristic for which the performance is monotone in the frequency of price changes. We conclude that dynamic pricing should be considered as a more favorable option in practice.