Robust Resource Allocation Decisions in Resource‐Constrained Projects*

The well‐known deterministic resource‐constrained project scheduling problem involves the determination of a predictive schedule (baseline schedule or pre‐schedule) of the project activities that satisfies the finish–start precedence relations and the renewable resource constraints under the objective of minimizing the project duration. This baseline schedule serves as a baseline for the execution of the project. During execution, however, the project can be subject to several types of disruptions that may disturb the baseline schedule. Management must then rely on a reactive scheduling procedure for revising or reoptimizing the baseline schedule. The objective of our research is to develop procedures for allocating resources to the activities of a given baseline schedule in order to maximize its stability in the presence of activity duration variability. We propose three integer programming–based heuristics and one constructive procedure for resource allocation. We derive lower bounds for schedule stability and report on computational results obtained on a set of benchmark problems.     

An Application of the AXIS Solution Framework to Multiple Objective Aggregate Production Planning

This paper provides data on the first application of a prototype of the AXIS solution framework. AXIS (algorithms combined with knowledge systems in an interactive sequence) is a framework for interactively combining structured algorithms that seek a best solution with knowledge-based expert systems that seek expert heuristic solutions. This paper tests the framework using an interactive multiple objective integer programming algorithm combined with heuristics taken from the domain of aggregate production planning. The results indicate the AXIS framework can be successful in generating high quality solutions, in vastly reduced solution times compared to the structured algorithms, at much lower costs compared to the expert heuristics working alone.     

On threshold BDDs and the optimal variable ordering problem

Many combinatorial optimization problems can be formulated as 0/1 integer programs (0/1 IPs). The investigation of the structure of these problems raises the following tasks: count or enumerate the feasible solutions and find an optimal solution according to a given linear objective function. All these tasks can be accomplished using binary decision diagrams (BDDs), a very popular and effective datastructure in computational logics and hardware verification. We present a novel approach for these tasks which consists of an output-sensitive algorithm for building a BDD for a linear constraint (a so-called threshold BDD) and a parallel AND operation on threshold BDDs. In particular our algorithm is capable of solving knapsack problems, subset sum problems and multidimensional knapsack problems. BDDs are represented as a directed acyclic graph. The size of a BDD is the number of nodes of its graph. It heavily depends on the chosen variable ordering. Finding the optimal variable ordering is an NP-hard problem. We derive a 0/1 IP for finding an optimal variable ordering of a threshold BDD. This 0/1 IP formulation provides the basis for the computation of the variable ordering spectrum of a threshold function. We introduce our new tool azove 2.0 as an enhancement to azove 1.1 which is a tool for counting and enumerating 0/1 points. Computational results on benchmarks from the literature show the strength of our new method.     

On statistical bounds of heuristic solutions to location problems

Combinatorial optimization problems such as locating facilities frequently rely on heuristics to minimize the objective function. The optimum is often sought iteratively; a criterion is therefore necessary to be able to decide when the procedure attains such an optimum. Pre-setting the number of iterations is dominant in OR applications, however, the fact that the quality of the solution cannot be ascertained by pre-setting the number of iterations makes it less preferable. A small and, almost dormant, branch of the literature suggests usage of statistical principles to estimate the minimum and its bounds as a tool to decide upon the stopping criteria and also to evaluate the quality of the solution. In the current work we have examined the functioning of statistical bounds obtained from four different estimators using simulated annealing. P-median test problems taken from Beasley’s OR-library were used for the sake of testing. Our findings show that the Weibull estimator and 2nd order Jackknife estimators are preferable and the requirement of sample size to be about 10. It should be noted that reliable statistical bounds are found to depend critically on a sample of heuristic solutions of high quality; we have therefore provided a simple statistic for checking the quality. The work finally concludes with an illustration of applying statistical bounds to the problem of locating 70 post distribution centers in a region in Sweden.     

Triple-solution approach for the strip packing problem with two-staged patterns

A triple-solution approach for the rectangular level strip packing problem is presented, where m item types with specified demands are packed in levels into a strip with definite width and infinite height to minimize the occupied height, with the constraint that the items in the same level cannot be placed one on top of the other. The approach contains two phases and considers three types of solutions. In phase one, two types of solutions, obtained respectively from solving residual problems using column generation and from looking ahead, are considered and the best is selected as phase-one solution. In phase two, an integer programming model is solved over the levels generated in phase-one to obtain phase-two solution. Finally the better one of the phase-one and phase-two solutions are selected. Computational results indicate that the approach is effective for both the instances with strongly heterogeneous items and those with weakly heterogeneous items.     

Discrete parallel machine makespan ScheLoc problem

Scheduling–Location (ScheLoc) problems integrate the separate fields of scheduling and location problems. In ScheLoc problems the objective is to find locations for the machines and a schedule for each machine subject to some production and location constraints such that some scheduling objective is minimized. In this paper we consider the discrete parallel machine makespan ScheLoc problem where the set of possible machine locations is discrete and a set of n jobs has to be taken to the machines and processed such that the makespan is minimized. Since the separate location and scheduling problem are both \(\mathcal {NP}\)-hard, so is the corresponding ScheLoc problem. Therefore, we propose an integer programming formulation and different versions of clustering heuristics, where jobs are split into clusters and each cluster is assigned to one of the possible machine locations. Since the IP formulation can only be solved for small scale instances we propose several lower bounds to measure the quality of the clustering heuristics. Extensive computational tests show the efficiency of the heuristics.     

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.     

Efficient Heuristics for MRP Lot Sizing with Variable Production/Purchasing Costs*

Two heuristics based on branch and bound (B&B) are developed to solve closed-loop material requirements planning (MRP) lot-sizing problems that have general product structures and variable costs. A “look ahead method'’(LAM) heuristic allows for variable production/purchasing costs and uses a single-level B&B procedure to rapidly improve lower bound values; thus, LAM efficiently uses computer-storage capacity and allows solution of larger problems. The “total average modification'’(TAM) heuristic uses B&B, applied level by level, and modified setup and carrying costs to solve the variable production/purchasing costs MRP lot-sizing problem. LAM and TAM are tested on problems and compared to heuristics in the literature. TAM may be used to solve large MRP lot-sizing problems encountered in practice.     

Distributed Decision‐Making in Supply Chains and Private E‐Marketplaces

This paper develops a distributed decision‐making framework for the players in a supply chain or a private e‐marketplace to collaboratively arrive at a global Pareto‐optimal solution. In this model, no player has complete knowledge about all the costs and constraints of the other players. The decision‐making framework employs an iterative procedure, based on the Integer L‐shaped method, in which a master problem is solved to propose global solutions, and each player uses his local problems to construct feasibility and optimality cuts on the master problem. The master problem is modeled as a mixed‐integer program, and the players' local problems are formulated as linear programs. Collaborative planning scenarios in private e‐marketplaces and in supply chains were formulated and solved for test data. The results show that this distributed model is able to achieve near‐optimal solutions considerably faster than the traditional centralized approach.     

Single facility scheduling with dual criteria: minimizing maximum tardiness subject to minimum number of tardy jobs

This paper considers the static single machine scheduling problem with the objective of minimizing the maximum tardiness of any job subject to the constraint that the total number of lardy jobs is minimum. Based on simple dominance conditions an o(n²) heuristic algorithm is proposed to find an approximate solution to this problem. The effectiveness of the proposed heuristic algorithm is empirically evaluated by solving a large number of problems and comparing them to the optimal solutions obtained through the branch and bound algorithm.     

Sequencing heuristics for dependent setups in a continuous process industry

In this paper we address the scheduling of Biaxially Oriented Polypropylene (BOPP) film production, which belongs to the plastics industry and is a continuous process. Scheduling problems in BOPP film production involve processing different thickness settings of films on a common facility. Customer orders of the same thickness setting are usually grouped together as a production batch and a setup time is incurred whenever the batch is switched. However, there is usually more than one batch for the same thickness setting because of the due date constraints of the orders. Therefore, there is a need to develop a batching and sequencing scheme that minimizes the total setup time, or equivalently the makespan, under the due date constraint. In this paper heuristics are developed to generate a near-optimal solution for the problem. The heuristics are evaluated by an optimal solution procedure and are tested by using the actual data from a plant making the BOPP film. Comparison of the heuristics with the results of the current system has demonstrated a significant reduction in total setup time.     

Allocation of Returned Products among Different Recovery Options through an Opportunity Cost–Based Dynamic Approach*

In a make‐to‐order product recovery environment, we consider the allocation decision for returned products decision under stochastic demand of a firm with three options: refurbishing to resell, parts harvesting, and recycling. We formulate the problem as a multiperiod Markov decision process (MDP) and present a linear programming (LP) approximation that provides an upper bound on the optimal objective function value of the MDP model. We then present two solution approaches to the MDP using the LP solution: a static approach that uses the LP solution directly and a dynamic approach that adopts a revenue management perspective and employs bid‐price controls technique where the LP is resolved after each demand arrival. We calculate the bid prices based on the shadow price interpretation of the dual variables for the inventory constraints and accept a demand if the marginal value is higher than the bid price. Since the need for solving the LP at each demand arrival requires a very efficient solution procedure, we present a transportation problem formulation of the LP via variable redefinitions and develop a one‐pass optimal solution procedure for it. We carry out an extensive numerical analysis to compare the two approaches and find that the dynamic approach provides better performance in all of the tested scenarios. Furthermore, the solutions obtained are within 2% of the upper bound on the optimal objective function value of the MDP model.     

An integrated approach for water resources decision making under interactive and compound uncertainties

In recent years, the issue of water allocation among competing users has been of great concern for many countries due to increasing water demand from population growth and economic development. In water management systems, the inherent uncertainties and their potential interactions pose a significant challenge for water managers to identify optimal water-allocation schemes in a complex and uncertain environment. This paper thus proposes a methodology that incorporates optimization techniques and statistical experimental designs within a general framework to address the issues of uncertainty and risk as well as their correlations in a systematic manner. A water resources management problem is used to demonstrate the applicability of the proposed methodology. The results indicate that interval solutions can be generated for the objective function and decision variables, and a number of decision alternatives can be obtained under different policy scenarios. The solutions with different risk levels of constraint violation can help quantify the relationship between the economic objective and the system risk, which is meaningful for supporting risk management. The experimental data obtained from the Taguchi's orthogonal array design are useful for identifying the significant factors affecting the means of total net benefits. Then the findings from the mixed-level factorial experiment can help reveal the latent interactions between those significant factors at different levels and their effects on the modeling response.     

FIRM EXPANSION THROUGH FRANCHISING: A MODEL AND SOLUTION PROCEDURES

This paper presents a practical model for firm expansion through franchising. The model allows the possibility of opening both company-owned and franchised stores. The objective is to maximize the expected returns to the franchisor from both types of stores, subject to the total capital outlay budget and the excess capacity available at each warehouse. A relaxation for this problem is studied and a heuristic solution procedure that makes use of this relaxation is developed. Experimental results over a wide range of problem structures show this solution methodology to be very effective, with gaps between feasible solution values and upper bounds generally in the 0 to 1 percent range. An efficient branch-and-bound code also is developed. This code is tested on problems with up to 100 potential store locations and 20 regions. It is found to be at least two orders of magnitude faster than a state-of-the-art commercial integer programming package.     

An access network design problem with end-to-end QoS constraints

In this paper, we present an access network design problem with end-to-end quality of service (QoS) requirement. The problem can be conceptualized as a two-level hierarchical location-allocation problem on the tree topology with nonlinear side constraints. The objective function of the nonlinear mixed integer programming model minimizes the total cost of switch and fiber cable, while satisfying demand within the prescribed level of QoS. By exploiting the inherent structure of the nonlinear QoS constraints, we develop linearization techniques for finding an optimal solution. Also, we devise an effective exact optimal algorithm within the context of disjunctive constraint generation. We present promising computational results that demonstrate the effectiveness of the proposed solution procedure.     

Exact methods in optimum disassembly sequence search for problems subject to sequence dependent costs

Disassembling complex products is formally approached via network representation and subsequent mathematical modeling, aimed at selecting a good or optimum sequence of disassembly operations. This is done via heuristics, metaheuristics or mathematical programming. In contrast with heuristics and metaheuristics, which select a near-optimum solution, mathematical programming guarantees the selection of the global optimum. This problem is relatively simple if the disassembly costs can be assumed sequence independent. In practice, however, sequence dependent disassembly costs are frequently encountered, which causes NP-completeness of the problem. Although methods, e.g., based on the two-commodity network flow approach, are available to solve this constrained asymmetric Traveling Salesperson problem rigorously, this requires the introduction of integer variables. In this paper, a modification of the two-commodity network flow approach is proposed, which reduces the number of integer variables. This is applied to product structures that can be represented by a disassembly precedence graph. It is demonstrated that use of integer variables is completely avoided by iteratively solving a binary integer linear programming problem. This appears to be more efficient than solving the corresponding integer linear programming problem. It is demonstrated, on the basis of some cases, that this method might provide the exact solution of problems with increased complexity compared to those discussed so far in the literature. This appears particularly useful for evaluating heuristic and metaheuristic approaches.     

SCHEDULING PARALLEL PROCESSORS WITH SETUP COSTS AND RESOURCE LIMITATIONS

An integer linear programming model is presented for the scheduling of n products on m identical machines. The particular problem studied is one that occurs frequently in the fiberglass and textile industries. The model incorporates setup costs, lost production costs, and overtime costs. Due to the structure of the model, integer solutions can be obtained by explicitly restricting only a small number of the integer variables. This allows those responsible for scheduling to solve realistically sized problems in an efficient manner. Computational results are provided for a set of generated test problems.     

Heuristics for scheduling in a flowshop with setup,processing and removal times separated

The problem of scheduling in a flowshop, where setup, processing and removal times are separable, is considered with the objective of minimizing makespan. Heuristic algorithms are developed by the introduction of simplifying assumptions into the scheduling problem under study. An improvement method is incorporated in the heuristics to enhance the quality of their solutions. The proposed heuristics and an existing heuristic are evaluated by a large number of randomly generated problems. The results of an extensive computational investigation for various values of parameters are presented.     

Maximizing target-temporal coverage of mission-driven camera sensor networks

In camera sensor networks (CSNs), the target coverage problem is of special importance since a sensor with different viewing directions captures distinct views for the same target. Furthermore, mission-driven monitoring applications in CSNs usually have special network lifetime requirements in which the limited battery lifetime of sensors probably can not sustain for full coverage. In this paper, based on effective-sensing model, we address three new coverage problems in mission-driven camera sensor networks, namely the target-temporal effective-sensing coverage with non-adjustable cameras (TEC-NC) problem, the target-temporal effective-sensing coverage with adjustable cameras (TEC-AC) problem, and the target-temporal effective-sensing coverage with fully-adjustable cameras (TEC-FAC) problem. Given a mission period, the common objective of the problems is to find a sleep-wakeup schedule such that the overall target-temporal coverage is maximized. For TEC-NC, we propose a 2-approximation algorithm and two new heuristics. We also design two greedy strategies, each of which can be combined with our solutions for TEC-NC to deal with TEC-AC and TEC-FAC, respectively. We finally conduct extensive experiments to evaluate the performance of the proposed algorithms, whose results indicate the proposed algorithms outperform the existing alternatives as well as are close to the theoretical optimum on average under certain conditions.     

The Comparative Statics of Constrained Optimization Problems

This paper develops and applies some new results in the theory of monotone comparative statics. Let f be a real‐valued function defined on R^l and consider the problem of maximizing f(x) when x is constrained to lie in some subset C of R^l. We develop a natural way to order the constraint sets C and find the corresponding restrictions on the objective function f that guarantee that optimal solutions increase with the constraint set. We apply our techniques to problems in consumer, producer, and portfolio theory. We also use them to generalize Rybcsynski's theorem and the LeChatelier principle.