基于中间表示规则替换的二进制翻译中间代码优化方法

动态二进制翻译在实现多源到多目标的程序翻译过程中,为屏蔽不同源平台间的硬件差异引入中间代码,采用内存虚拟策略进行实现,但同时带来中间代码膨胀问题。传统的中间代码优化方法主要采用对冗余指令进行匹配删除的方法。将优化重点聚焦在针对特殊指令匹配的中间表示规则替换上,提出了一种基于中间表示规则替换的二进制翻译中间代码优化方法。该方法针对中间代码膨胀所呈现的几种典型情景,描述了中间表示替换规则,并将以往应用在后端代码优化上的寄存器直接映射策略应用在此处。通过建立映射公式,实现了将原来的内存虚拟操作替换为本地寄存器操作,从而降低了中间代码膨胀率。使用SPEC CPU2006测试集进行了实验,验证了此优化方法的正确性和有效性。测试用例在优化前和优化后的执行结果一致,验证了优化方法的正确性;优化后测试用例的中间代码平均缩减率达到32.59%,验证了优化方法的有效性。     

Algorithms for solving the conditional covering problem on paths

Consider the conditional covering problem on an undirected graph, where each node represents a site that must be covered by a facility, and facilities may only be established at these nodes. Each facility can cover all sites that lie within some common covering radius, except the site at which it is located. Although this problem is difficult to solve on general graphs, there exist special structures on which the problem is easily solvable. In this paper, we consider the special case in which the graph is a simple path. For the case in which facility location costs do not vary based on the site, we derive characteristics of the problem that lead to a linear‐time shortest path algorithm for solving the problem. When the facility location costs vary according to the site, we provide a more complex, but still polynomial‐time, dynamic programming algorithm to find the optimal solution. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005.     

Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function

We consider open‐shop scheduling problems where operation‐processing times are a convex decreasing function of a common limited nonrenewable resource. The scheduler's objective is to determine the optimal job sequence on each machine and the optimal resource allocation for each operation in order to minimize the makespan. We prove that this problem is NP‐hard, but for the special case of the two‐machine problem we provide an efficient optimization algorithm. We also provide a fully polynomial approximation scheme for solving the preemptive case. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Time minimizing flows in directed networks

An important class of network flow problems is that class for which the objective is to minimize the cost of the most expensive unit of flow while obtaining a desired total flow through the network. Two special cases of this problem have been solved, namely, the bottleneck assignment problem and time-minimizing transportation problem. This paper addresses the more general case which we shall refer to as the time-minimizing network flow problem. Associated with each arc is an arc capacity (static) and a transferral time. The objective is to find a maximal flow for which the length (in time) of the longest path carrying flow is minimized. The character of the problem is discussed and a solution algorithm is presented.     

An easy solution for a special class of fixed charge problems

The fixed charge problem is a mixed integer mathematical programming problem which has proved difficult to solve in the past. In this paper we look at a special case of that problem and show that this case can be solved by formulating it as a set-covering problem. We then use a branch-and-bound integer programming code to solve test fixed charge problems using the setcovering formulation. Even without a special purpose set-covering algorithm, the results from this solution procedure are dramatically better than those obtained using other solution procedures.     

The continuous multiple-modular design problem

In this article we extend our previous work on the continuous single-module design problem to the multiple-module case. It is assumed that there is a fixed cost associated with each additional module used. The Kuhn–Tucker conditions characterize local optima among which there is a global optimum. Modules are associated with partitions and a special class, guillotine partitions, are characterized. Branch-and-bound, partial enumeration, and heuristic procedures for finding optimum or good guillotine partitions are discussed and illustrated with examples.     

Flowshop sequencing problem with ordered processing time matrices: A general case

The ordered matrix flow shop problem with no passing of jobs is considered. In an earlier paper, the authors have considered a special case of the problem and have proposed a simple and efficient algorithm that finds a sequence with minimum makespan for a special problem. This paper considers a more general case. This technique is shown to be considerably more efficient than are existing methods for the conventional flow shop problems.     

Designing a screening experiment for highly reliable products

Within a reasonable life‐testing time, how to improve the reliability of highly reliable products is one of the great challenges to today's manufacturers. By using a resolution III experiment together with degradation test, Tseng, Hamada, and Chiao (1995) presented an interesting case study of improving the reliability of fluorescent lamps. However, in conducting such an experiment, they did not address the problem of how to choose the optimal settings of variables, such as sample size, inspection frequency, and termination time for each run, which are influential to the correct identification of significant factors and the experimental cost. Assuming that the product's degradation paths satisfy Wiener processes, this paper proposes a systematic approach to the aforementioned problem. First, an intuitively appealing identification rule is proposed. Next, under the constraints of a minimum probability of correct decision and a maximum probability of incorrect decision of the proposed identification rule, the optimum test plan (including the determinations of inspection frequency, sample size, and termination time for each run) can be obtained by minimizing the total experimental cost. An example is provided to illustrate the proposed method. © 2002 Wiley Periodicals, Inc. Naval Research Logistics 49: 514–526, 2002; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/nav.10024     

On some sequencing problems

The (mxn) sequencing problem may be characterized as follows: There are m machines which can produce a piece consisting of n parts. Each part has a determined order in which it is processed through the machines. It is assumed that each machine cannot deal with more than one part at a time and that the processing required for each part can be accomplished only on one machine. That is, the machines are all specialized so that alternate machines for the same processing on a part is not possible. The problem is to find the best production plan consisting in sequencing the different parts so as to make the whole amount of time from the beginning of work till the piece is completed the shortest possible. Such a plan is called an optimum one. In the first 4 sections of this paper, the problem (2xn) is solved for the (2xn) case in which the order in which parts come on the machine is not constrained by further assumptions. The remainder of the paper then takes up: 1) the (3xn) problem of Bellman-Johnson (viz. the technological processing order through the machine is the same for all parts) for several new special cases; 2) the 2xn problem of sequencing when delay times must also be considered; and, 3) some properties of an approximating method for solving (mxn) problems, including a delineation of cases when the approximating method will yield optimal solutions.     

An inspection game: Taking account of fulfillment probabilities of players' aims

This paper deals with an inspection game of customs and a smuggler. The customs can take two options of assigning a patrol or not. The smuggler has two strategies of shipping its cargo of contraband or not. Two players have several opportunities to take actions during a limited number of days. When both players do, there are some possibilities that the customs captures the smuggler and, simultaneously, the smuggler possibly makes a success of the smuggling. If the smuggler is captured or there remain no days for playing the game, the game ends. In this paper, we formulate the problem into a multi‐stage two‐person zero‐sum stochastic game and investigate some characteristics of the equilibrium solution, some of which are given in a closed form in a special case. There have been some studies so far on the inspection game. However, some consider the case that the smuggler has only one opportunity of smuggling or the perfect‐capture case that the customs can certainly arrest the smuggler on patrol, and others think of a recursive game without the probabilities of fulfilling the players' purposes. In this paper, we consider the inspection game taking account of the fulfillment probabilities of the players' aims. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

On the inspection game

The Inspection Game is a multistage game between a customs inspector and a smuggler, first studied by Melvin Dresher and Michael Maschler in the 1960s. An extension allowing the smuggler to act more than once, treated by Sakaguchi in a special case, is solved. Also, a more natural version of Sakaguchi's problem is solved in the special case where the smuggler may act at each stage. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 327–334, 1998     

New results on rendezvous search on the interval

In a rendezvous search problem, two players are placed in a network and must try to meet each other in the least possible expected time. We look at rendezvous search on a discrete interval in which the players are initially placed using independent draws (usually assumed to be from the same distribution). Some optimal solutions are known if this distribution is uniform, and also for certain other special types of distribution. In this article, we present two new results. First, we characterize the complete set of solutions for the uniform case, showing that all optimal strategies must have two specific properties (namely, of being swept and strictly geodesic). Second, we relate search strategies on the interval to proper binary trees, and use this correspondence to derive a recurrence relation for solutions to the symmetric rendezvous problem for any initial distribution. This relation allows us to solve any such problem computationally by dynamic programming. Finally, some ideas for future research are discussed. © Wiley Periodicals, Inc. Naval Research Logistics 60: 454–467, 2013     

Using real options analysis to value reoptimization options in the shifting bottleneck heuristic

The reoptimization procedure within the shifting bottleneck (SB) involves reevaluation of all previously scheduled toolgroup subproblems at each iteration of the SB heuristic. A real options analysis (ROA) model is developed to value the option to reoptimize in the SB heuristic, such that reoptimization only occurs when it is most likely to lead to a schedule with a lower objective function. To date, all ROA models have sought to value options financially (i.e., in terms of monetary value). The ROA model developed in this paper is completely original in that it has absolutely no monetary basis. The ROA methodologies presented are shown to greatly outperform both full and no reoptimization approaches with respect to both computation time and total weighted tardiness. © 2006 Wiley Periodicals, Inc. Naval Research Logistics, 2006     

Integrating decisions with advance supply information in an assemble-to-order system

We study a periodic-review assemble-to-order (ATO) system with multiple components and multiple products, in which the inventory replenishment for each component follows an independent base-stock policy and stochastic product demands are satisfied according to a First-Come-First-Served rule. We assume that the replenishment for various component suffers from lead time uncertainty. However, the decision maker has the so-called advance supply information (ASI) associated with the lead times and thus can take advantage of the information for system optimization. We propose a multistage stochastic integer program that incorporates ASI to address the joint optimization of inventory replenishment and component allocation. The optimal base-stock policy for the inventory replenishment is determined using the sample average approximation algorithm. Also, we provide a modified order-based component allocation (MOBCA) heuristic for the component allocation. We additionally consider a special case of the variable lead times where the resulting two-stage stochastic programming model can be characterized as a single-scenario case of the proposed multistage model. We carry out extensive computational studies to quantify the benefits of integrating ASI into joint optimization and to explore the possibility of employing the two-stage model as a relatively efficient approximation scheme for the multistage model.     

Production and transport logistics scheduling with two transport mode choices

This paper considers a new class of scheduling problems arising in logistics systems in which two different transportation modes are available at the stage of product delivery. The mode with the shorter transportation time charges a higher cost. Each job ordered by the customer is first processed in the manufacturing facility and then transported to the customer. There is a due date for each job to arrive to the customer. Our approach integrates the machine scheduling problem in the manufacturing stage with the transportation mode selection problem in the delivery stage to achieve the global maximum benefit. In addition to studying the NP‐hard special case in which no tardy job is allowed, we consider in detail the problem when minimizing the sum of the total transportation cost and the total weighted tardiness cost is the objective. We provide a branch and bound algorithm with two different lower bounds. The effectiveness of the two lower bounds is discussed and compared. We also provide a mathematical model that is solvable by CPLEX. Computational results show that our branch and bound algorithm is more efficient than CPLEX. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005     

Monotone optimal preventive maintenance policies for stochastically failing equipment

This paper examines various models for maintenance of a machine operating subject to stochastic deterioration. Three alternative models are presented for the deterioration process. For each model, in addition to the replacement decision, the option exists of performing preventive maintenance. The effect of this maintenance is to “slow” the deterioration process. With an appropriate reward structure imposed on the processes, the models are formulated as continuous time Markov decision processes. the optimality criterion being the maximization of expected discounted reward earned over an infinite time horizon. For each model conditions are presented under which the optimal maintenance policy exhibits the following monotonic structure. First, there exists a control limit rule for replacement. That is, there exists a number i* such that if the state of machine deterioration exceeds i* the optimal policy replaces the machine by a new machine. Secondly, prior to replacement the optimal level of preventive maintenance is a nonincreasing function of the state of machine deterioration. The conditions which guarantee this result have a cost/benefit interpretation.     

The sequencing of “related” jobs

Given n jobs and a single facility, and the fact that a subset of jobs are “related” to each other in such a manner that regardless of which job is completed first, its utility is hampered until all other jobs in the same subset are also completed, it is desired to determine the sequence which minimizes the cost of tardiness. The special case of pairwise relationship among all jobs is easily solved. An algorithm for the general case is given through a dynamic programming formulation.     

Scheduling of depalletizing and truck loading operations in a food distribution system

This paper studies a scheduling problem arising in a beef distribution system where pallets of various types of beef products in the warehouse are first depalletized and then individual cases are loaded via conveyors to the trucks which deliver beef products to various customers. Given each customer's demand for each type of beef, the problem is to find a depalletizing and truck loading schedule that fills all the demands at a minimum total cost. We first show that the general problem where there are multiple trucks and each truck covers multiple customers is strongly NP‐hard. Then we propose polynomial‐time algorithms for the case where there are multiple trucks, each covering only one customer, and the case where there is only one truck covering multiple customers. We also develop an optimal dynamic programming algorithm and a heuristic for solving the general problem. By comparing to the optimal solutions generated by the dynamic programming algorithm, the heuristic is shown to be capable of generating near optimal solutions quickly. © 2003 Wiley Periodicals, Inc. Naval Research Logistics, 2003     

Capacitated selection problem

Optimizing the selection of resources to accomplish a set of tasks involves evaluating the tradeoffs between the cost of maintaining the resources necessary to accomplish the tasks and the penalty cost associated with unfinished tasks. We consider the case where resources are categorized into types, and limits (capacity) are imposed on the number of each type that can be selected. The objective is to minimize the sum of penalty costs and resource costs. This problem has several practical applications including production planning, new product design, menu selection and inventory management. We develop a branch‐and‐bound algorithm to find exact solutions to the problem. To generate bounds, we utilize a dual ascent procedure which exploits the special structure of the problem. Information from the dual and recovered primal solutions are used to select branching variables. We generate strong valid inequalities and use them to fix other variables at each branching step. Results of tests performed on reasonably sized problems are presented. © 1999 John Wiley & Sons, Inc. Naval Research Logistics 46: 19–37, 1999     

Instant transportation solutions

This paper presents direct noniterative methods for solving such known problems as shoploading and aggregate scheduling. There is given a simple optimal rule for the shop-loading problem which is quite surprising. The crucial point in solving this problem is what not to assign rather than what to assign. The development of those methods was possible since the discussed problems can be converted into a special transportation model where the given cost coefficients c_ij assume a form cij = ui + uj.