A SINGLE-MACHINE SCHEDULING MODEL WITH FIXED-INTERVAL DELIVERIES

We consider an environment where a production facility modeled as a single machine needs to assign delivery dates to several orders and find a feasible sequence. Tardy jobs are not allowed. The delivery dates are to be at prespecified fixed intervals. The objective is to minimize the due date penalty and the cost of earliness. We provide a dynamic programming-based solution procedure that runs in polynomial time. We develop several dominance results that reduced the computational requirement by an order of magnitude in our computational study.     

Static-dynamic uncertainty strategy for a single-item stochastic inventory control problem

We consider a single-stage inventory system facing non-stationary stochastic demand of the customers in a finite planning horizon. Motivated by the practice, the replenishment times need to be determined and frozen once and for all at the beginning of the horizon while decisions on the exact replenishment quantities can be deferred until the replenishment time. This operating scheme is refereed to as a “static-dynamic uncertainty” strategy in the literature [3]. We consider dynamic fixed-ordering and linear end-of-period holding costs, as well as dynamic penalty costs, or service levels. We prove that the optimal ordering policy is a base stock policy for both penalty cost and service level constrained models. Since an exponential exhaustive search based on dynamic programming yields the optimal ordering periods and the associated base stock levels, it is not possible to compute the optimal policy parameters for longer planning horizons. Thus, we develop two heuristics. Numerical experiments show that both heuristics perform well in terms of solution quality and scale-up efficiently; hence, any practically relevant large instance can be solved in reasonable time. Finally, we discuss how our results and heuristics can be extended to handle capacity limitations and minimum order quantity considerations.     

Penalty guided genetic search for redundancy optimization in multi-state series-parallel power system

This paper presents a genetic algorithm (GA) for parallel redundancy optimization in series-parallel power systems exhibiting multi-state behavior, optimizing the reliability subject to constraints. The components are binary and chosen from a list of products available in the market, and are being characterized by their feeding capacity, reliability, cost and weight. System reliability is defined as the ability to satisfy consumer demand and is presented as a piecewise cumulative load curve. In GA, to handle infeasible solutions penalty strategies are used. Penalty technique keep a certain amount of infeasible solutions in each generation so as to enforce genetic search towards an optimal solution from sides of, both, feasible and infeasible regions. We here present a dynamic adaptive penalty function which helps the algorithm to search efficiently for optimal/near optimal solution. To evaluate system reliability, a fast procedure, based on universal generating function, is used. An example considering a multi-state series-parallel power system is solved considering both homogeneous and heterogeneous types of redundancy. Also an example considering price discounts is solved. The effectiveness of the penalty function and the proposed algorithm is studied and shown graphically.     

社会共治下的食品企业失信经营问题三方演化博弈研究

针对食品企业失信经营的问题,借鉴日常活动理论,从机会、动机和控制方法三个方面,对企业失信经营进行了分析。在监管机构传统监管与共治监管两种方式下,基于演化博弈方法,构建了食品企业、消费者、监管机构的三方演化博弈模型。依据企业失信经营获利的大小,从博弈均衡上对食品企业失信经营问题进行了研究,并运用Matlab对博弈模型进行了分析验证。通过对两种监管方式的效率和应用范围进行深入分析,研究结果表明处罚和赔偿可有效降低食品企业失信经营的动机;当企业失信经营动机较小时,传统监管方式即可有效威慑食品企业,从而使其选择诚信经营策略;当企业失信动机较大时,即便使用共治监管方式仍无法有效监管食品企业失信经营。     

炼钢连铸生产调度问题的两阶段遗传算法

将炼钢连铸生产过程抽象为混合流水车间,建立了0-1型混合整数线性规划调度模型。模型将严格连续浇注作为等式约束,并通过分段惩罚来平衡炉次的驻留时间。在对模型进行Benders分解的基础上,提出了将GA与LP结合的两阶段遗传算法。在算法设计中,提出了一种新的染色体编码来表示炉次设备指派与排序方案,给出了相应的遗传操作方法。算法的第一阶段通过最小化设备析取冲突来寻找高质量的种群,第二阶段通过求解线性规划模型来指导遗传算法的迭代过程。基于生产实际数据的仿真实验表明,该算法能够有效求解炼钢连铸生产调度问题。     

Hierarchical Multi‐skill Resource Assignment in the Telecommunications Industry

We formulate a discrete time Markov decision process for a resource assignment problem for multi‐skilled resources with a hierarchical skill structure to minimize the average penalty and waiting costs for jobs with different waiting costs and uncertain service times. In contrast to most queueing models, our application leads to service times that are known before the job is actually served but only after it is accepted and assigned to a server. We formulate the corresponding Markov decision process, which is intractable for problems of realistic size due to the curse of dimensionality. Using an affine approximation of the bias function, we develop a simple linear program that yields a lower bound for the minimum average costs. We suggest how the solution of the linear program can be used in a simple heuristic and illustrate its performance in numerical examples and a case study.     

Optimal lot sizing under continuous price decrease

An important characteristic of high-tech industries is decreasing component prices over time. In the personal computer industry, some component prices decline at a rate of 1% per week. This paper develops an inventory model for products experiencing continuous decrease in unit price. We develop an accurate closed-form approximate solution to the model. Our results indicate that declining prices lead to substantial decrease in the optimal cycle time and much frequent ordering. This explains the heavy emphasis on just-in-time inventory management practiced by successful companies in high-tech industries. While previous models attributed the success of just-in-time policies to reduced holding cost and improved quality, under declining prices a substantial source of savings becomes lower costs of raw materials which is significant part of cost in these industries. We illustrate the results of the model with a numerical example and perform sensitivity analysis.     

Contaminated consignment simulation to support risk-based inspection design

Invasive nonnative plant pests can cause extensive environmental and economic damage and are very difficult to eradicate once established. Phytosanitary inspections that aim to prevent biological invasions by limiting movement of nonnative plant pests across borders are a critical component of the biosecurity continuum. Inspections can also provide valuable information about when and where plant pests are crossing national boundaries. However, only a limited portion of the massive volume of goods imported daily can be inspected, necessitating a highly targeted, risk-based strategy. Furthermore, since inspections must prioritize detection and efficiency, their outcomes generally cannot be used to make inferences about risk for cargo pathways as a whole. Phytosanitary agencies need better tools for quantifying pests going undetected and designing risk-based inspection strategies appropriate for changing operational conditions. In this research, we present PoPS (Pest or Pathogen Spread) Border, an open-source consignment inspection simulator for measuring inspection outcomes under various cargo contamination scenarios to support recommendations for inspection protocols and estimate pest slippage rates. We used the tool to estimate contamination rates of historical interception data, quantify tradeoffs in effectiveness and workload for inspection strategies, and identify vulnerabilities in sampling protocols as changes in cargo configurations and contamination occur. These use cases demonstrate how this simulation approach permits testing inspection strategies and measuring quantities that would otherwise be impossible in a field-based setting. This work represents the first steps toward a decision support tool for creating dynamic inspection protocols that respond to changes in available resources, workload, and commerce trends.     

DESIGNING INSPECTION STRATEGIES FOR UNCERTAIN ENVIRONMENTS

This paper considers the problems of designing inspection strategies for production systems terms in the presence of environmental uncertainty. The framework for determining information priorities to support inspection system planning is presented in the contaxt of a generic production system that encompasses the characteristics of many real-world serial production systems. The impact on the design decision of five key variables is considered: quality of producton processes, quality of inspection procedures, penalty cost for undetected defective units, relative cost of improving process vs. inspection, and shape of the cost functions for process and inspection enhancement. The framework for analysis involves varying factors over two or three orders of magnitude to determine optimal inspection strategies across a wide range of environments These results are used to compare design decisions made in the presence of environmental uncertainty using expected-opportunity-cost and minimization-of-maximum-opportunity-cost approaches. Design strategies are identified for situations ranging from complete lack of knowledge about the environment through increasing levels of information. Information-gathering priorities are established, and the impact on the design decision of this additional information is assayed.     

Optimal Inspection of Imports to Prevent Invasive Pest Introduction

The United States imports more than 1 billion live plants annually—an important and growing pathway for introduction of damaging nonnative invertebrates and pathogens. Inspection of imports is one safeguard for reducing pest introductions, but capacity constraints limit inspection effort. We develop an optimal sampling strategy to minimize the costs of pest introductions from trade by posing inspection as an acceptance sampling problem that incorporates key features of the decision context, including (i) simultaneous inspection of many heterogeneous lots, (ii) a lot‐specific sampling effort, (iii) a budget constraint that limits total inspection effort, (iv) inspection error, and (v) an objective of minimizing cost from accepted defective units. We derive a formula for expected number of accepted infested units (expected slippage) given lot size, sample size, infestation rate, and detection rate, and we formulate and analyze the inspector's optimization problem of allocating a sampling budget among incoming lots to minimize the cost of slippage. We conduct an empirical analysis of live plant inspection, including estimation of plant infestation rates from historical data, and find that inspections optimally target the largest lots with the highest plant infestation rates, leaving some lots unsampled. We also consider that USDA‐APHIS, which administers inspections, may want to continue inspecting all lots at a baseline level; we find that allocating any additional capacity, beyond a comprehensive baseline inspection, to the largest lots with the highest infestation rates allows inspectors to meet the dual goals of minimizing the costs of slippage and maintaining baseline sampling without substantial compromise.     

基于动态博弈的闭环供应链回收质量控制研究

本文采用三阶段的动态博弈模型,研究了在单个制造商和单个销售商构成的分散式闭环供应链中,占主导地位的制造商如何制定质量处罚比例和质量抽检比例,从而对销售商回收的废旧产品数量和质量实施引导和控制。本文建立了相应的模型并给出了最优解,并通过算例讨论了不同的废旧产品缺陷率和监督成本对双方决策的影响。     

Inventory‐Related Compensation in Decentralized Organizations

We consider a principal agent problem in a decentralized organization. The agent holds private precontracting information with respect to an uncertain demand in a single period setting. Being head of a profit center, his only task is to determine the optimal order quantity. We show that using a profit share as the only performance measure to incentivize the agent creates agency costs. In fact, offering a menu of profit‐sharing contracts to the agent to pick from, requires rent payments to motivate the agent to always choose the desired contract. This result still holds if a fixed payment is added. Using an inventory‐related component as a third measure, however, allows one to solve the agency problem and to achieve first best outcomes. Precisely, each contract needs to specify a bonus or a penalty conditioned on the inventory level at the end of the selling season combined with a profit share and a fixed pay. The paper not only demonstrates that first best can be achieved in the described setting, it also provides a theoretical explanation for the observed practice of using inventory‐related compensation elements, such as service‐level agreements, in organizations.     

Call Center Delay Announcement Using a Newsvendor‐Like Performance Criterion

The problem of estimating delays experienced by customers with different priorities, and the determination of the appropriate delay announcement to these customers, in a multi‐class call center with time varying parameters, abandonments, and retrials is considered. The system is approximately modeled as an M(t)/M/s(t) queue with priorities, thus ignoring some of the real features like abandonments and retrials. Two delay estimators are proposed and tested in a series of simulation experiments. Making use of actual state‐dependent waiting time data from this call center, the delay announcements from the estimated delay distributions that minimize a newsvendor‐like cost function are considered. The performance of these announcements is also compared to announcing the mean delay. We find that an Erlang distribution‐based estimator performs well for a range of different under‐announcement penalty to over‐announcement penalty ratios.     

Contractors’ and Agency Decisions and Policy Implications in A+B Bidding

The focus of this study is on the A+B transportation procurement mechanism, which uses the proposed cost (A component) and the proposed time (B component) to score contractors’ bids. Empirical studies have shown that this mechanism shortens project durations. We use normative models to study the effect of certain discretionary parameters set by state transportation agencies on contractors’ equilibrium bidding strategies, winner selection, and actual completion times. We model the bidding environment in detail including multi‐dimensional bids, contractors’ uncertainty about completion times, and reputation cost. The latter refers to a private penalty that accrues to tardy contractors from increased cost of posting bonds and reduced prospects of winning future projects. Our model explains why contractors may skew line‐item bids and why winners frequently finish earlier than bid. It has several policy implications as well. For example, we recommend that agencies set the daily incentive, disincentive, and road user cost to be equal and not cap incentives. This is a departure from current practice, where incentives are often capped and weaker than penalties. Furthermore, we show that agencies may be justified in setting daily road user cost strictly smaller than the true cost of traffic disruption during construction.     

DELIVERY GUARANTEES AND THE INTERDEPENDENCE OF MARKETING AND OPERATIONS

Delivery guarantees are an important element in a customer satisfaction program. When setting delivery guarantees, a firm must consider customer expectations as well as operational constraints. We develop a profit‐maximization model in which a firm's sales organization, with incomplete information on operations' status, solicits orders and quotes delivery dates. If obtained, orders are processed in a make‐to‐order facility, after which revenue is received, minus tardiness penalty if the delivery was later than quoted. We specify conditions for an optimal log‐linear decision rule and provide exact expressions for its effect on arrival rate, mean processing time, and mean cycle time.     

基于改进差分进化算法的VRP-SDPTW研究

整合前向物流和逆向物流,提出带时间窗的同时送货和取货的车辆路径问题(VRP-SDPTW)的混合整数规划数学模型.首次提出改进的差分进化算法(IDE)求解该问题,算法对不可行解设计惩罚机制,当基因值超过规定的范围时,设计基于整数序规范的辅助算子解决变异问题,设计一种随进化代数自动更新的交叉率.数值实验表明,改进的差分进化算法能有效地求解VRP-SDPTW.     

Aligning DNA Sequences to Minimize the Change in Protein

We study an alignment model for coding DNA sequences recently proposed by J. Hein that takes into account both DNA and protein information, and attempts to minimize the total amount of evolution at both DNA and protein levels. Assuming that the gap penalty function is affine, we design a quadratic time dynamic programming algorithm for the model. Although the algorithm theoretically solves an open question of Hein, its running time is impractical because of the large constant factor embedded in the quadratic time complexity function. We therefore consider a mild simplification named Context-free Codon Alignment of Hein's model and present a much more efficient algorithm for the simplified model. The algorithms have been implemented and tested on both real and simulated sequences, and it is found that they produce almost identical alignments in most cases. Furthermore, we extend our model and design a heuristic algorithm to handle frame-shift errors and overlapping frames in coding regions.     

Risk-Based Integrity and Inspection Modeling (RBIIM) of Process Components/System

Process plants deal with hazardous (highly flammable and toxic) chemicals at extreme conditions of temperature and pressure. Proper inspection and maintenance of these facilities is paramount for the maintenance of safe and continuous operation. This article proposes a risk-based methodology for integrity and inspection modeling (RBIIM) to ensure safe and fault-free operation of the facility. This methodology uses a gamma distribution to model the material degradation and a Bayesian updating method to improve the distribution based on actual inspection results. The method deals with the two cases of perfect and imperfect inspections. The measurement error resulting from imperfect inspections is modeled as a zero-mean, normally distributed random process. The risk is calculated using the probability of failure and the consequence is assessed in terms of cost as a function of time. The risk function is used to determine an optimal inspection and replacement interval. The calculated inspection and replacement interval is subsequently used in the design of an integrity inspection plan. Two case studies are presented: the maintenance of an autoclave and the maintenance of a pipeline segment. For the autoclave, the interval between two successive inspections is found to be 19 years. For the pipeline, the next inspection is due after 5 years from now. Measurements taken at inspections are used in estimating a new degradation rate that can then be used to update the failure distribution function.     

Optimal semi-online algorithm for scheduling with rejection on two uniform machines

In this paper we consider a semi-online scheduling problem with rejection on two uniform machines with speed 1 and s≥1, respectively. A sequence of independent jobs are given and each job is characterized by its size (processing time) and its penalty, in the sense that, jobs arrive one by one and can be either rejected by paying a certain penalty or assigned to some machine. No preemption is allowed. The objective is to minimize the sum of the makespan of schedule, which is yielded by all accepted jobs and the total penalties of all rejected ones. Further, two rejection strategies are permitted thus an algorithm can propose two different schemes, from which the better solution is chosen. For the above version, we present an optimal semi-online algorithm H that achieves a competitive ratio ρ _H (s) as a piecewise function in terms of the speed ratio s.