A heuristic algorithm for minimizing maintenance workforce level

We develop a heuristic algorithm for minimizing the workforce level required to accommodate all the maintenance jobs requested within a specific time interval. Each maintenance job has its own release and due dates as well as the required man-days, and must be scheduled in a noninterrupted time interval, i.e. without preemption. However, the duration of each job is not fixed, but to be determined within a specific range. We show that this problem can be seen as a variant of the two-dimensional bin-packing problem with some additional constraints. We develop a non-linear mixed integer programming model for the proposed problem, and employ some well-known bin-packing algorithms to develop an efficient heuristic algorithm. In order to evaluate the performance of the proposed heuristic, we present a computationally efficient scheme for getting a good lower bound for the actual minimum. The computational experiment shows that the proposed heuristic algorithm performs quite satisfactorily in practice.     

Pricing and Operational Performance in Discretionary Services

In many services, for example, website or landscape design, the value or quality derived by a customer depends upon the service time, and this valuation differs across customers. Customers procure the service based on the expected value to be delivered, prices charged, and the timeliness of service. We investigate the performance of the optimal pricing scheme as well as two commonly used pricing schemes (fixed fee and time‐based pricing) for such services on important dimensions such as revenue, demand served, and utilization. We propose a novel model that captures the above features and wherein both service rate and demand are endogenous and functions of the pricing scheme. In particular, service time is an outcome of the pricing scheme adopted and the heterogeneous valuations of customers, unlike in the queueing‐based pricing literature. We find that the service system may benefit from a greater variance in consumer valuations, and the performance of pricing schemes is impacted by the shape of the distribution of customers' valuation of service time and the responsiveness desired by customers. Both the fixed fee and time‐based schemes do well relative to the optimal pricing scheme in terms of revenue in many plausible scenarios, but there are substantial differences between the pricing schemes in some important operational metrics. For instance, the fixed fee scheme serves more customers and has higher utilization than the time‐based scheme. We also explore variants of the fixed and time‐based schemes that have better revenue performance and show that the two‐part tariff which is a combination of fixed and time‐based pricing can do as well as the optimal scheme in terms of revenue.     

Race to idle or not: balancing the memory sleep time with DVS for energy minimization

Reducing energy consumption is a critical problem in most of the computing systems today. Among all the computing system components, processor and memory are two significant energy consumers. Dynamic voltage scaling is typically applied to reduce processor energy while sleep mode is usually injected to trim memory’s leakage energy. However, in the memory architecture with multiple cores sharing memory, in order to optimize the system-wide energy, these two classic techniques are difficult to be directly combined due to the complicated interactions. In this work, we explore the coordination of the multiple cores and the memory, and present systematic analysis for minimizing the system-wide energy based on different system models and task models. For tasks with common release time, optimal schemes are presented for the systems both with and without considering the static power of the cores. For agreeable deadline tasks, different dynamic programming-based optimal solutions are proposed for negligible and non-negligible static power of cores. For the general task model, this paper proposes a heuristic online algorithm. Furthermore, the scheme is extended to handle the problem when the transition overhead between the active and sleep modes is considered. The optimality of the proposed schemes for common release time and agreeable deadline tasks are proved. The validity of the proposed heuristic scheme is evaluated through experiments. Experimental results confirm the superiority of the heuristic scheme in terms of the energy saving improvement compared to the most related existing work.     

An effective iterated greedy algorithm for the mixed no-idle permutation flowshop scheduling problem

In the no-idle flowshop, machines cannot be idle after finishing one job and before starting the next one. Therefore, start times of jobs must be delayed to guarantee this constraint. In practice machines show this behavior as it might be technically unfeasible or uneconomical to stop a machine in between jobs. This has important ramifications in the modern industry including fiber glass processing, foundries, production of integrated circuits and the steel making industry, among others. However, to assume that all machines in the shop have this no-idle constraint is not realistic. To the best of our knowledge, this is the first paper to study the mixed no-idle extension where only some machines have the no-idle constraint. We present a mixed integer programming model for this new problem and the equations to calculate the makespan. We also propose a set of formulas to accelerate the calculation of insertions that is used both in heuristics as well as in the local search procedures. An effective iterated greedy (IG) algorithm is proposed. We use an NEH-based heuristic to construct a high quality initial solution. A local search using the proposed accelerations is employed to emphasize intensification and exploration in the IG. A new destruction and construction procedure is also shown. To evaluate the proposed algorithm, we present several adaptations of other well-known and recent metaheuristics for the problem and conduct a comprehensive set of computational and statistical experiments with a total of 1750 instances. The results show that the proposed IG algorithm outperforms existing methods in the no-idle and in the mixed no-idle scenarios by a significant margin.     

Facility Dispersion Problems Under Capacity and Cost Constraints

The MAX-MIN dispersion problem, which arises in the placement of undesirable facilities, involves selecting a specified number of sites among a set of potential sites so as to maximize the minimum distance between any pair of selected sites. We consider different versions of this dispersion problem where each potential site has an associated storage capacity and a storage cost. A typical problem in this context is to choose a subset of potential sites so that the total capacity of the chosen sites is at least a given value, the total storage cost is within the specified budget and the minimum distance between any pair of chosen sites is maximized. Since these constrained optimization problems are NP-hard in general, we consider whether there are efficient approximation algorithms for them with good performance guarantees. Our results include approximation algorithms for some versions, approximation schemes for some geometric versions and polynomial algorithms for special cases. We also present results that bring out the intrinsic difficulty of obtaining near-optimal solutions to some versions.     

Single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity consideration

This article studies a single-machine scheduling with deteriorating jobs and aging effects under an optional maintenance activity. We assume that after maintenance activity, the machine will revert to its initial condition and the aging effects will start anew. Moreover, due to the restriction of budget of maintenance, the limitation of the maintenance frequency on the machine is assumed to be known in advance. The optional maintenance activity of this study means that the starting time of the maintenance activity is unknown in advance. It can be scheduled immediately after the processing of any job that has been completed. Therefore, the planner must to make decision on whether or when to schedule the maintenance activity during the scheduling horizon to optimal the performance measures. The objective is to minimize the makespan. We first show that the addressed problem is NP-hard in the strong sense. Then a fully polynomial-time approximation scheme (FPTAS) for the proposed problem is presented.     

Separator-based data reduction for signed graph balancing

Polynomial-time data reduction is a classical approach to hard graph problems. Typically, particular small subgraphs are replaced by smaller gadgets. We generalize this approach to handle any small subgraph that has a small separator connecting it to the rest of the graph. The problem we study is the NP-hard Balanced Subgraph problem, which asks for a 2-coloring of a graph that minimizes the inconsistencies with given edge labels. It has applications in social networks, systems biology, and integrated circuit design. The data reduction scheme unifies and generalizes a number of previously known data reductions, and can be applied to a large number of graph problems where a coloring or a subset of the vertices is sought. To solve the instances that remain after reduction, we use a fixed-parameter algorithm based on iterative compression with a very effective heuristic speedup. Our implementation can solve biological real-world instances exactly for which previously only approximations were known. In addition, we present experimental results for financial networks and random networks.     

Linear solution schemes for Mean-SemiVariance Project portfolio selection problems: An application in the oil and gas industry

We study the Mean-SemiVariance Project (MSVP) portfolio selection problem, where the objective is to obtain the optimal risk-reward portfolio of non-divisible projects when the risk is measured by the semivariance of the portfolio׳s Net-Present Value (NPV) and the reward is measured by the portfolio׳s expected NPV. Similar to the well-known Mean-Variance portfolio selection problem, when integer variables are present (e.g., due to transaction costs, cardinality constraints, or asset illiquidity), the MSVP problem can be solved using Mixed-Integer Quadratic Programming (MIQP) techniques. However, conventional MIQP solvers may be unable to solve large-scale MSVP problem instances in a reasonable amount of time. In this paper, we propose two linear solution schemes to solve the MSVP problem; that is, the proposed schemes avoid the use of MIQP solvers and only require the use of Mixed-Integer Linear Programming (MILP) techniques. In particular, we show that the solution of a class of real-world MSVP problems, in which project returns are positively correlated, can be accurately approximated by solving a single MILP problem. In general, we show that the MSVP problem can be effectively solved by a sequence of MILP problems, which allow us to solve large-scale MSVP problem instances faster than using MIQP solvers. We illustrate our solution schemes by solving a real MSVP problem arising in a Latin American oil and gas company. Also, we solve instances of the MSVP problem that are constructed using data from the PSPLIB library of project scheduling problems.     

The maximum dispersion problem

In the maximum dispersion problem, a given set of objects has to be partitioned into a number of groups. Each object has a non-negative weight and each group has a target weight, which may be different for each group. In addition to meeting the target weight of each group, all objects assigned to the same group should be as dispersed as possible with respect to some distance measure between pairs of objects. Potential applications for this problem come from such diverse fields as the problem of creating study groups or the design of waste collection systems. We develop and compare two different (mixed-) integer linear programming formulations for the problem. We also study a specific relaxation that enables us to derive tight bounds that improve the effectiveness of the formulations. Thereby, we obtain an upper bound by finding in an auxiliary graph subsets of given size with minimal diameter. A lower bound is derived based on the relation of the optimal solution of the relaxation to the chromatic number of a series of auxiliary graphs. Finally, we propose an exact solution scheme for the maximum dispersion problem and present extensive computational experiments to assess its efficiency.     

Improving robustness of next-hop routing

A weakness of next-hop routing is that following a link or router failure there may be no routes between some source-destination pairs, or packets may get stuck in a routing loop as the protocol operates to establish new routes. In this article, we address these weaknesses by describing mechanisms to choose alternate next hops. Our first contribution is to model the scenario as the following tree augmentation problem. Consider a mixed graph where some edges are directed and some undirected. The directed edges form a spanning tree pointing towards the common destination node. Each directed edge represents the unique next hop in the routing protocol. Our goal is to direct the undirected edges so that the resulting graph remains acyclic and the number of nodes with outdegree two or more is maximized. These nodes represent those with alternative next hops in their routing paths. We show that tree augmentation is NP-hard in general and present a simple \(\frac{1}{2}\)-approximation algorithm. We also study 3 special cases. We give exact polynomial-time algorithms for when the input spanning tree consists of exactly 2 directed paths or when the input graph has bounded treewidth. For planar graphs, we present a polynomial-time approximation scheme when the input tree is a breadth-first search tree. To the best of our knowledge, tree augmentation has not been previously studied.     

Subcontracting price schemes for order acceptance and scheduling

In this paper we study subcontracting price schemes between a subcontractor and a firm that are engaged in subcontracting of heterogeneous orders with distinct due dates, revenues, and processing times. We assume that the subcontractor proposes the subcontracting pricing and the firm follows by determining the subcontracted orders by solving its order acceptance and scheduling problem. When the subcontractor adopts a linear pricing scheme, we find the firm׳s optimal decisions and develop an algorithm to derive the subcontractor׳s own optimal pricing. We then design a fixed pricing with transfer payment scheme and a quantity discount pricing scheme to coordinate the firm׳s and subcontractor׳s decisions. We examine if the subcontractor can make a higher profit using either of these schemes than the linear pricing scheme, and if they will induce the firm to make decisions that lead to system-wide optimal outcomes.     

Subset sum problems with digraph constraints

We introduce and study optimization problems which are related to the well-known Subset Sum problem. In each new problem, a node-weighted digraph is given and one has to select a subset of vertices whose total weight does not exceed a given budget. Some additional constraints called digraph constraints and maximality need to be satisfied. The digraph constraint imposes that a node must belong to the solution if at least one of its predecessors is in the solution. An alternative of this constraint says that a node must belong to the solution if all its predecessors are in the solution. The maximality constraint ensures that no superset of a feasible solution is also feasible. The combination of these constraints provides four problems. We study their complexity and present some approximation results according to the type of input digraph, such as directed acyclic graphs and oriented trees.     

需求响应下解决交叉补贴的阶梯电价方案研究——基于社会福利最大化视角

我国电价交叉补贴问题非常严重，其无论从经济效率还是公平上而言都是不合理的，必须尽快解决。通过对现行电价政策分析，阶梯电价政策可以解决交叉补贴问题，但现行方案效果不明显，因此需要调整。不仅如此，由于各档次用户对电价变化的需求响应程度存在差异，调整阶梯电价来解决交叉补贴的方案有许多，故存在一个社会福利最大化的解决方案。本文以社会福利最大化为目标，调整各档用户的电价，同时引入拉格朗日函数，设计出最优解决交叉补贴问题的阶梯电价方案，得到各档相应的电价比值。结果表明，当分档电价比值为1：1.62：2.41时社会福利存在极大值，此时阶梯电价方案是众多方案中的最优方案，社会福利全年增加约为702.00亿元。此方案在解决交叉补贴问题的基础上还兼顾了用户间公平和承受能力，对当前电价改革具有重要参考价值。     

考虑消费者双通道心理账户和参照依赖的动态定价问题研究

为分析消费者双通道心理账户及参照依赖行为对企业长期利润的影响,本文探讨了在一般支付、提前支付及延迟支付方案下的动态定价问题。采用了离散时间动态规划分析思路,讨论了两周期模型在不同支付方案下最优价格、最优利润的关系,进一步将动态定价行为扩展到了无限期的情形,分析了在各种支付方案下的稳态价格,结果表明当需求函数是线性时,提前支付与延迟支付下的稳态价格要大于一般支付下的稳态价格;当初始参考价格较高(较低)时,最优价格策略类似于撇脂定价策略(渗透定价策略)。最后通过数值分析,比较了双通道心理账户各参数对不同支付方案长期总利润的影响,并总结了厂商如何选择最优支付方案以获取更高利润的建议。该思路对基于行为的动态定价研究具有一定的借鉴意义。     

Approximate event detection over multi-modal sensing data

Composite event detection is one of the fundamental tasks for heterogeneous wireless sensor networks (WSNs). Multi-modal data generated by heterogeneous sensors bring new challenges for composite event monitoring in heterogeneous WSNs. By exploiting the correlations between different types of data, the approximate composite event detection problem is investigated in this paper. The optimal transmitting scheme problem is proposed to calculate the optimal transmitting scheme with minimum cost on the constraint that the confidence of the composite event must exceed the threshold. The optimal transmitting scheme problem is proved to belong to NP-complete. A dynamic programming based algorithm is presented for simple linear confidence combination operators, which runs in pseudo-polynomial time. The greedy based approximate algorithm is also designed for general confidence combination operators and the approximate ratio is proved to be 2 for “+” as the confidence combination operator. The simulation results show that our algorithms can reduce energy consumption significantly.     

An Analysis of Monopolistic and Competitive Take‐Back Schemes for WEEE Recycling

We study two prevailing types of take‐back schemes for electrical and electronic equipment waste recycling: monopolistic and competitive. We address key market and operating factors that make one scheme preferable to the other from the viewpoints of recyclers, manufacturers, and consumers. To this end, we model competitive decision making in both take‐back schemes as two‐stage sequential games between competing manufacturers and recyclers. Deriving and computing equilibria, we find that the competitive take‐back scheme often accomplishes a win–win situation, that is, lower product prices, and higher recycler and manufacturer profits. Exceptionally, recyclers prefer the monopolistic scheme when the substitutability level between the manufacturers' original products is high or economies of scale in recycling are very strong. We show that consolidation of the recycling industry could benefit all stakeholders when the economies of scale in recycling are strong, provided that manufacturer's products are not highly substitutable. Higher collection rates also render recycler consolidation desirable for all stakeholders. We also identify a potential free rider problem in the monopolistic scheme when recyclers differ in operational efficiency, and propose mechanisms to eliminate the discrepancy. We show that our results and insights are robust to the degree of competition within the recycling industry.     

Alignments with non-overlapping moves,inversions and tandem duplications in <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>4</Superscript>) time

Sequence alignment is a central problem in bioinformatics. The classical dynamic programming algorithm aligns two sequences by optimizing over possible insertions, deletions and substitutions. However, other evolutionary events can be observed, such as inversions, tandem duplications or moves (transpositions). It has been established that the extension of the problem to move operations is NP-complete. Previous work has shown that an extension restricted to non-overlapping inversions can be solved in O(n ³) with a restricted scoring scheme. In this paper, we show that the alignment problem extended to non-overlapping moves can be solved in O(n ⁵) for general scoring schemes, O(n ⁴log n) for concave scoring schemes and O(n ⁴) for restricted scoring schemes. Furthermore, we show that the alignment problem extended to non-overlapping moves, inversions and tandem duplications can be solved with the same time complexities. Finally, an example of an alignment with non-overlapping moves is provided. A preliminary version of this paper appeared in the Proceedings of COCOON 2007, LNCS, vol. 4598, pp. 151–164.     

Piecewise linear approximations for the static–dynamic uncertainty strategy in stochastic lot-sizing

In this paper, we develop a unified mixed integer linear modelling approach to compute near-optimal policy parameters for the non-stationary stochastic lot sizing problem under static–dynamic uncertainty strategy. The proposed approach applies to settings in which unmet demand is backordered or lost; and it can accommodate variants of the problem for which the quality of service is captured by means of backorder penalty costs, non-stockout probabilities, or fill rate constraints. This approach has a number of advantages with respect to existing methods in the literature: it enables seamless modelling of different variants of the stochastic lot sizing problem, some of which have been previously tackled via ad hoc solution methods and some others that have not yet been addressed in the literature; and it produces an accurate estimation of the expected total cost, expressed in terms of upper and lower bounds based on piecewise linearisation of the first order loss function. We illustrate the effectiveness and flexibility of the proposed approach by means of a computational study.     

Reliable Ad Hoc Routing Based on Mobility Prediction

Reliability is a very important issue in Mobile Ad hoc NETworks (MANETs). Shortest paths are usually used to route packets in MANETs. However, a shortest path may fail quickly, because some of the wireless links along a shortest path may be broken shortly after the path is established due to mobility of mobile nodes. Rediscovering routes may result in substantial data loss and message exchange overhead. In this paper, we study reliable ad hoc routing in the urban environment. Specifically, we formulate and study two optimization problems. In the minimum Cost Duration-bounded Path (CDP) routing problem, we seek a minimum cost source to destination path with duration no less than a given threshold. In the maximum Duration Cost-bounded Path (DCP) routing problem, we seek a maximum duration source to destination path with cost no greater than a given threshold. We use a waypoint graph to model the working area of a MANET and present an offline algorithm to compute a duration prediction table for the given waypoint graph. An entry in the duration prediction table contains the guaranteed worst-case duration of the corresponding wireless link. We then present an efficient algorithm which computes a minimum cost duration-bounded path, using the information provided in the duration prediction table. We also present a heuristic algorithm for the DCP routing problem. In addition, we show that the proposed prediction and routing schemes can be easily applied for designing reliable ad hoc routing protocols. Simulation results show that our mobility prediction based routing algorithms lead to higher network throughput and longer average path duration, compared with the shortest path routing. This research was supported in part by ARO grant W911NF-04-1-0385 and NSF grant CCF-0431167. The information reported here does not reflect the position or the policy of the federal government.     

Comparison of Subsidy Schemes for Reducing Waiting Times in Healthcare Systems

This study analyzes subsidy schemes that are widely used in reducing waiting times for public healthcare service. We assume that public healthcare service has no user fee but an observable delay, while private healthcare service has a fee but no delay. Patients in the public system are given a subsidy s to use private service if their waiting times exceed a pre‐determined threshold t. We call these subsidy schemes (s, t) policies. As two extreme cases, the (s, t) policy is called an unconditional subsidy scheme if t = 0, and a full subsidy scheme if s is equal to the private service fee. There is a fixed budget constraint so that a scheme with larger s has a larger t. We assess policies using two criteria: total patient cost and serviceability (i.e., the probability of meeting a waiting time target for public service). We prove analytically that, if patients are equally sensitive to delay, a scheme with a smaller subsidy outperforms one with a larger subsidy on both criteria. Thus, the unconditional scheme dominates all other policies. Using empirically derived parameter values from the Hong Kong Cataract Surgery Program, we then compare policies numerically when patients differ in delay sensitivity. Total patient cost is now unimodal in subsidy amount: the unconditional scheme still yields the lowest total patient cost, but the full subsidy scheme can outperform some intermediate policies. Serviceability is unimodal too, and the full subsidy scheme can outperform the unconditional scheme in serviceability when the waiting time target is long.