A FRAMEWORK FOR MACHINE SCHEDULING PROBLEMS WITH CONTROLLABLE PROCESSING TIMES

This is a study of single and parallel machine scheduling problems with controllable processing time for each job. The processing time for job j depends on the position of the job in the schedule and is a function of the number of resource units allocated to its processing. Processing time functions and processing cost functions are allowed to be nonlinear. The scheduling problems considered here have important applications in industry and include many of the existing scheduling models as special cases. For the single machine problem, the objective is minimization of total compression costs plus a scheduling measure. The scheduling measures include makespan, total flow time, total differences in completion times, total differences in waiting times, and total earliness and tardiness with a common due date for all jobs. Except when the total earliness and tardiness measure is involved, each case the problem is solved efficiently. Under an assumption typically satisfied in just-in-time systems, the problem with total earliness and tardiness measure is also solved efficiently. Finally, for a large class of processing time functions; parallel machine problems with total flow time and total earliness and tardiness measures are solved efficiently. In each case we reduce the problem to a transportation problem.     

Optimal Policy for a Stochastic Scheduling Problem with Applications to Surgical Scheduling

We consider the stochastic, single‐machine earliness/tardiness problem (SET), with the sequence of processing of the jobs and their due‐dates as decisions and the objective of minimizing the sum of the expected earliness and tardiness costs over all the jobs. In a recent paper, Baker ( 2014 ) shows the optimality of the Shortest‐Variance‐First (SVF) rule under the following two assumptions: (a) The processing duration of each job follows a normal distribution. (b) The earliness and tardiness cost parameters are the same for all the jobs. In this study, we consider problem SET under assumption (b). We generalize Baker's result by establishing the optimality of the SVF rule for more general distributions of the processing durations and a more general objective function. Specifically, we show that the SVF rule is optimal under the assumption of dilation ordering of the processing durations. Since convex ordering implies dilation ordering (under finite means), the SVF sequence is also optimal under convex ordering of the processing durations. We also study the effect of variability of the processing durations of the jobs on the optimal cost. An application of problem SET in surgical scheduling is discussed.     

Just-in-time scheduling with controllable processing times on parallel machines

We study scheduling problems with controllable processing times on parallel machines. Our objectives are to maximize the weighted number of jobs that are completed exactly at their due date and to minimize the total resource allocation cost. We consider four different models for treating the two criteria. We prove that three of these problems are NP\mathcal{NP} -hard even on a single machine, but somewhat surprisingly, the problem of maximizing an integrated objective function can be solved in polynomial time even for the general case of a fixed number of unrelated parallel machines. For the three NP\mathcal{NP} -hard versions of the problem, with a fixed number of machines and a discrete resource type, we provide a pseudo-polynomial time optimization algorithm, which is converted to a fully polynomial time approximation scheme.     

Inventory Rationing for Multiple Class Demand under Continuous Review

We consider how a firm should ration inventory to multiple classes in a stochastic demand environment with partial, class‐dependent backlogging where the firm incurs a fixed setup cost when ordering from its supplier. We present an infinite‐horizon, average cost criterion Markov decision problem formulation for the case with zero lead times. We provide an algorithm that determines the optimal rationing policy, and show how to find the optimal base‐stock reorder policy. Numerical studies indicate that the optimal policy is similar to that given by the equivalent deterministic problem and relies on tracking both the current inventory and the rate that backorder costs are accumulating. Our study of the case of non‐zero lead time shows that a heuristic combining the optimal, zero lead time policy with an allocation policy based on a single‐period profit management problem is effective.     

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.     

OPTIMAL PROJECT SEQUENCING WITH RECOURSE AT A SCARCE RESOURCE

We develop a dynamic prioritization policy to optimally allocate a scarce resource among K projects, only one of which can be worked on at a time. When the projects' delay costs differ, the problem (a “restless bandit”) has not been solved in general. We consider the policy of working on the project with the highest expected delay loss as if the other project was completely finished first (although recourse is allowed). This policy is optimal if: (1) the delay cost increases with the delay regardless of the performance state, (2) costs are not discounted (or, discounting is dominated by delay costs), (3) projects are not abandoned based on their performance state during processing at the scarce resource, and (4) there are no stochastic delays. These assumptions are often fulfilled for processing at specialized resources, such as tests or one‐off analyses.     

LINEAR PROGRAMMING WITH DISCRETE STOCHASTIC RESOURCES: AN ALTERNATIVE APPROACH ACCOUNTING FOR INFEASIBILITY*

In this paper an alternative to, or extension of, the chance-constrained method of stochastic programming is presented whereby an expected cost of infeasibility is included in the objective function. The problem is to select a solution to implement before the available resources are known where the adaption of a non-feasible solution to the resources available involves a system cost. While increasing the amount of computation required, the model enables the decision maker to more effectively trade off increased payoff for decreased likelihood of feasibility.     

随机需求下基于“自营+外包”模式的配送中心选址-配送问题研究

针对顾客需求量不确定情况下末端配送中心选址及提前备货问题，提出了基于“自营+外包”配送模式的配送中心选址-配送问题。以自营配送中心的固定运行成本、提前备货成本和各种场景下的自营配送成本、外包配送成本以及缺货损失成本的期望值之和最小化为目标，建立了两阶段连续型随机规划模型。第一阶段确定自营配送中心的选址位置和各个配送中心的提前备货量；第二阶段确定各种场景下的自营配送货运量、外包配送货运量和客户点的缺货量等，使总成本期望值达到最小。基于Monte Carlo抽样理论设计了求解模型的样本均值近似方法；以及求解大规模问题L-shaped分解算法。通过模拟算例验证了两阶段随机规划模型的优越性和样本均值近似方法的有效性；并对自营配送中心固定运行成本、单位商品的自营配送成本和外包配送成本等进行灵敏度分析，得到了不同参数对应的最优配送策略，结果表明，正常情况下“自营+外包”配送模式是企业的最佳选择。本文同时将配送中心选址和提前备货量作为随机规划模型的第一阶段决策变量，可以帮助企业降低物流成本、提高顾客的满意度。     

一类网络扩张的机会约束模型与算法

在不确定环境中的机会约束下,怎样去增加一组边的容量到一个指定的瓶颈容量,而使网络瓶颈扩张的费用最小.带有随机单位扩张费用的网络瓶颈容量扩张问题,可以根据一些概率机会约束规则,列出它的机会约束规划模型的通用表达式.将网络瓶颈容量算法、随机模拟方法和遗传算法合成在一起,设计出该问题的混合智能通用算法.最后,给出数值案例.     

The benefit of receding horizon control: Near-optimal policies for stochastic inventory control

In this paper we address the single-item, single-stocking point, non-stationary stochastic lot-sizing problem under backorder costs. It is well known that the (s, S) policy provides the optimal control for such inventory systems. However the computational difficulties and the nervousness inherent in (s, S) paved the way for the development of various near-optimal inventory control policies. We provide a systematic comparison of these policies and present their expected cost performances. We further show that when these policies are used in a receding horizon framework the cost performances improve considerably and differences among policies become insignificant.     

The optimal value range problem for the Interval (immune) Transportation Problem

We address the problem of finding the range of the optimal cost of a transportation problem when supply and demand vary over an interval. We consider the specific version of a transportation problem with supply inequality constraints and demand equality constraints under the assumption that the transportation costs are immune against the transportation paradox. We investigate some theoretical properties of the problem which constitute the basis of a novel solution algorithm. Our results show that the proposed algorithm hugely outperforms the best existing solution approaches.     

Cross‐Training with Imperfect Training Schemes

Cross‐training workers is one of the most efficient ways of achieving flexibility in manufacturing and service systems for increasing responsiveness to demand variability. However, it is generally the case that cross‐trained employees are not as productive on a specific task as employees who were originally trained for that task. Also, the productivity of the cross‐trained workers depends on when they are cross‐trained. In this work, we consider a two‐stage model to analyze the effects of variations in productivity levels on cross‐training policies. We define a new metric called achievable capacity and show that it plays a key role in determining the structure of the problem. If cross‐training can be done in a consistent manner, the achievable capacity is not affected when the training is done, which implies that the cross‐training decisions are independent of the opportunity cost of lost demand and are based on a trade‐off between cross‐training costs at different times. When the productivities of workers trained at different times differ, there is a three‐way trade‐off between cross‐training costs at different times and the opportunity cost of lost demand due to lost achievable capacity. We analyze the effects of variability and show that if the productivity levels of workers trained at different times are consistent, the decision maker is inclined to defer the cross‐training decisions as the variability of demand or productivity levels increases. However, when the productivities of workers trained at different times differ, an increase in the variability may make investing more in cross‐training earlier more preferable.     

Production stage allocation problem in large corporations

This paper studies a strategic-level decision problem on assigning production stages to geographically distributed subsidiaries in a large corporation so as to minimize the fixed cost and the expected value of the production/transportation costs under stochastic demands of customers. The influence of the economies and diseconomies of scale on unit production cost is considered. A nonlinear mixed integer programming model is designed for this problem. A local branching based solution method and a particle swarm optimization based solution method are developed for solving the model. Computational tests on real world data of Shanghai Volkswagen Auto Corp. are conducted. The results show that the proposed model can save about 2.5% of its revenue by comparing with the current decisions.     

Optimal Control of Replenishment and Substitution in an Inventory System with Nonstationary Batch Demand

We study an inventory system in which a supplier supplies demand using two mutually substitutable products over a selling season of T periods, with a single replenishment opportunity at the beginning of the season. As the season starts, customer orders arrive in each period, for either type of products, following a nonstationary Poisson process with random batch sizes. The substitution model we consider combines the usual supplier‐driven and customer‐driven schemes, in that the supplier may choose to offer substitution, at a discount price, or may choose not to; whereas the customer may or may not accept the substitution when it is offered. The supplier's decisions are the supply and substitution rules in each period throughout the season, and the replenishment quantities for both products at the beginning of the season. With a stochastic dynamic programming formulation, we first prove the concavity of the value function, which facilitates the solution to the optimal replenishment quantities. We then show that the optimal substitution follows a threshold rule, and establish the monotonicity of the thresholds over time and with respect to key cost parameters. We also propose a heuristic exhaustive policy, and illustrate its performance through numerical examples.     

Supplier Selection for Framework Agreements in Humanitarian Relief

In this study, we consider the supplier selection problem of a relief organization that wants to establish framework agreements (FAs) with a number of suppliers to ensure quick and cost‐effective procurement of relief supplies in responding to sudden‐onset disasters. Motivated by the FAs in relief practice, we focus on a quantity flexibility contract in which the relief organization commits to purchase a minimum total quantity from each framework supplier over a fixed agreement horizon, and, in return, the suppliers reserve capacity for the organization and promise to deliver items according to pre‐specified agreement terms. Due to the uncertainties in demand locations and amounts, it may be challenging for relief organizations to assess candidate suppliers and the offered agreement terms. We use a scenario‐based approach to represent demand uncertainty and develop a stochastic programming model that selects framework suppliers to minimize expected procurement and agreement costs while meeting service requirements. We perform numerical experiments to understand the implications of agreement terms in different settings. The results show that supplier selection decisions and costs are generally more sensitive to the changes in agreement terms in settings with high‐impact disasters. Finally, we illustrate the applicability of our model on a case study.     

On step fixed-charge transportation problem

The fixed-charge problem is a nonlinear programming problem of practical interest in business and industry. One of its variations is the fixed-charge transportation problem (FCTP) where fixed cost is incurred for every route that is used in the solution, along with the variable cost that is proportional to the amount shipped. That cost structure causes the value of the objective function Z to also behave like a step function. Each time we open or close a route the objective function jumps a step. The step fixed-charge transportation problem (SFCTP) is a variation of the FCTP where the fixed cost is in the form of a step function dependent on the load in a given route. While the value of the objective function Z in the FCTP is a step function, the introduction of the step fixed cost in the SFCTP results in the objective function Z being itself a step function with many more steps. Fixed-charge problems are usually solved using sophisticated analytical or computer software. This paper discusses the theory of SFCTP and presents a computationally simple heuristic algorithm for solving small SFCTPs.     

The facility location problem with Bernoulli demands

This paper presents the facility location problem with Bernoulli demands. In this capacitated discrete location stochastic problem the goal is to define an a priori solution for the locations of the facilities and for the allocation of customers to the operating facilities that minimizes the sum of the fixed costs of the open facilities plus the expected value of the recourse function. The problem is formulated as a two-stage stochastic program and two different recourse actions are considered. For each of them, a closed form is presented for the recourse function and a deterministic equivalent formulation is obtained for the case in which the probability of demand is the same for all customers. Numerical results from computational experiments are presented and analyzed.     

Asymptotically optimal policy for stochastic job shop scheduling problem to minimize makespan

This paper studies the large-scale stochastic job shop scheduling problem with general number of similar jobs, where the processing times of the same step are independently drawn from a known probability distribution, and the objective is to minimize the makespan. For the stochastic problem, we introduce the fluid relaxation of its deterministic counterpart, and define a fluid schedule for the fluid relaxation. By tracking the fluid schedule, a policy is proposed for the stochastic job shop scheduling problem. The expected value of the gap between the solution produced by the policy and the optimal solution is proved to be O(1), which indicates the policy is asymptotically optimal in expectation.     

带工期指派的产品服务系统订单随机调度问题研究

针对由一个制造工厂和多个区域服务中心组成的服务型制造企业,研究了考虑生产时间和服务时间均具有随机性且工期可指派的产品服务系统（PSS）订单调度问题。首先以最小化订单提前、误工和工期指派费用的期望总额为目标构建问题的优化模型,然后分析目标函数近似值的最优性条件,据此提出加权最短平均生产时间排序规则,并结合该规则与插入邻域局部搜索设计了启发式算法对问题进行求解,最后通过数值仿真验证算法的可行性和有效性。研究表明,提前费用偏差对PSS订单调度与工期指派决策的影响很小,因此企业管理者无需准确估计库存费用也能制定出比较有效的PSS订单调度策略;而工期指派费用偏差对决策结果的影响非常大,因此企业管理者在决策时必须谨慎估计该项费用。     

An hierarchal location—allocation problem

We consider a 2-hierarchal location-allocation problem when p₁ health centers and p₂ hospitals are to be located among n potential locations so as to minimize the total weighted travel distance. We consider the possibility of the referral of θ (0 ≤ θ ≤ 1) proportion of patients from a health center to a hospital. For a graph with certain properties, we extend the notion of a median of a graph to an hierarchal median set. We show how the 2-hierarchal location-allocation problem may be solved as a 2-hierarchal vertex median set problem. We formulate the problem as a mathematical programming problem, suggest five heuristic procedures to solve the problem and report some computational experience. Although we consider the hierarchal location-allocation problem with reference to a health care delivery system, the results of this paper have wide application.