Heuristic procedures for a stochastic batch service problem

This paper considers a multi-class batch service problem that involves a class-dependent waiting cost and a service cost in determining customer batch sizes. Unlike a fixed service cost used widely in standard models, the service cost considered in this work is incurred only if the total service time is over the capacity. We formulate this problem as an infinite horizon Markov decision process, and exploit its structural properties to establish theoretical results, including bounds on the optimal action space. We use the results to improve the value iteration procedure. Furthermore, we design heuristic algorithms for large problems. The numerical experiments demonstrate that the class-dependent waiting cost has a considerable influence on the optimal customer batch size. Finally, we evaluate the efficiency of the proposed value iteration procedure and the quality of the heuristic solutions.     

Design of Controllable Batch Processes in the Presence of Uncertainty

Design of controllable batch processes can be more challenging than continuous processes because of their unsteady nature of operation. The operating strategy of a batch process is characterized by trajectories of manipulated variables. This precludes the use of conventional controllability measures in evaluating the controllability of a given batch process design. Short process development cycles typically accredited to batch processes lead to uncertainty in the model formulation. Integrated approach to batch process design and control addresses the problem of controllability of a batch process during the design phase. This is best achieved by treating the problem as a dynamic optimization problem with time invariant (design) and time variant (operating) variables. The method proposed in this paper uses the decomposition feature of Generalized Benders Decomposition (GBD) to evolve a 2-level nested optimization problem (primal and master), one involving time variant decision (operating) variables and the other involving time invariant decision (design) variables. To enhance the computational efficiency, a relaxed LP formulation of the master problem is proposed. This variant of GBD, termed as ExGBD, is guaranteed to converge to the optimum for convex problems. A simple batch reactor design problem has been chosen to demonstrate ExGBD.     

The static stochastic knapsack problem with normally distributed item sizes

This paper develops exact and heuristic algorithms for a stochastic knapsack problem where items with random sizes may be assigned to a knapsack. An item’s value is given by the realization of the product of a random unit revenue and the random item size. When the realization of the sum of selected item sizes exceeds the knapsack capacity, a penalty cost is incurred for each unit of overflow, while our model allows for a salvage value for each unit of capacity that remains unused. We seek to maximize the expected net profit resulting from the assignment of items to the knapsack. Although the capacity is fixed in our core model, we show that problems with random capacity, as well as problems in which capacity is a decision variable subject to unit costs, fall within this class of problems as well. We focus on the case where item sizes are independent and normally distributed random variables, and provide an exact solution method for a continuous relaxation of the problem. We show that an optimal solution to this relaxation exists containing no more than two fractionally selected items, and develop a customized branch-and-bound algorithm for obtaining an optimal binary solution. In addition, we present an efficient heuristic solution method based on our algorithm for solving the relaxation and empirically show that it provides high-quality solutions.     

A queueing model for general group screening policies and dynamic item arrivals

Classification of items as good or bad can often be achieved more economically by examining the items in groups rather than individually. If the result of a group test is good, all items within it can be classified as good, whereas one or more items are bad in the opposite case. Whether it is necessary to identify the bad items or not, and if so, how, is described by the screening policy. In the course of time, a spectrum of group screening models has been studied, each including some policy. However, the majority ignores that items may arrive at random time epochs at the testing center in real life situations. This dynamic aspect leads to two decision variables: the minimum and maximum group size. In this paper, we analyze a discrete-time batch-service queueing model with a general dependency between the service time of a batch and the number of items within it. We deduce several important quantities, by which the decision variables can be optimized. In addition, we highlight that every possible screening policy can, in principle, be studied, by defining the dependency between the service time of a batch and the number of items within it appropriately.     

Applications of bulk queues to group testing models with incomplete identification

A population of items is said to be “group-testable”, (i) if the items can be classified as “good” and “bad”, and (ii) if it is possible to carry out a simultaneous test on a batch of items with two possible outcomes: “Success” (indicating that all items in the batch are good) or “failure” (indicating a contaminated batch). In this paper, we assume that the items to be tested arrive at the group-testing centre according to a Poisson process and are served (i.e., group-tested) in batches by one server. The service time distribution is general but it depends on the batch size being tested. These assumptions give rise to the bulk queueing model M/G^(m,M)/1, where m and M(>m) are the decision variables where each batch size can be between m and M. We develop the generating function for the steady-state probabilities of the embedded Markov chain. We then consider a more realistic finite state version of the problem where the testing centre has a finite capacity and present an expected profit objective function. We compute the optimal values of the decision variables (m, M) that maximize the expected profit. For a special case of the problem, we determine the optimal decision explicitly in terms of the Lambert function.     

A single machine batch scheduling problem with bounded batch size

We address a single-machine batch scheduling problem to minimize total flow time. Processing times are assumed to be identical for all jobs. Setup times are assumed to be identical for all batches. As in many practical situations, batch sizes may be bounded. In the first setting studied in this paper, all batch sizes cannot exceed a common upper bound. In the second setting, all batch sizes share a common lower bound. An optimal solution consists of the number of batches and their (integer) size. We introduce an efficient solution for both problems.     

Solving non-linear portfolio optimization problems with the primal-dual interior point method

Stochastic programming is recognized as a powerful tool to help decision making under uncertainty in financial planning. The deterministic equivalent formulations of these stochastic programs have huge dimensions even for moderate numbers of assets, time stages and scenarios per time stage. So far models treated by mathematical programming approaches have been limited to simple linear or quadratic models due to the inability of currently available solvers to solve NLP problems of typical sizes. However stochastic programming problems are highly structured. The key to the efficient solution of such problems is therefore the ability to exploit their structure. Interior point methods are well-suited to the solution of very large non-linear optimization problems. In this paper we exploit this feature and show how portfolio optimization problems with sizes measured in millions of constraints and decision variables, featuring constraints on semi-variance, skewness or non-linear utility functions in the objective, can be solved with the state-of-the-art solver.     

Sample size selection in optimization methods for machine learning

This paper presents a methodology for using varying sample sizes in batch-type optimization methods for large-scale machine learning problems. The first part of the paper deals with the delicate issue of dynamic sample selection in the evaluation of the function and gradient. We propose a criterion for increasing the sample size based on variance estimates obtained during the computation of a batch gradient. We establish an complexity bound on the total cost of a gradient method. The second part of the paper describes a practical Newton method that uses a smaller sample to compute Hessian vector-products than to evaluate the function and the gradient, and that also employs a dynamic sampling technique. The focus of the paper shifts in the third part of the paper to L ₁-regularized problems designed to produce sparse solutions. We propose a Newton-like method that consists of two phases: a (minimalistic) gradient projection phase that identifies zero variables, and subspace phase that applies a subsampled Hessian Newton iteration in the free variables. Numerical tests on speech recognition problems illustrate the performance of the algorithms.     

Just-in-time replenishment decisions for assembly manufacturing with investor-supplied finance

While JIT ideas have been enthusiastically embraced by manufacturing practitioners, the small replenishment batch sizes advocated are difficult to reconcile with the standard management science cost trade-off approach. The difficulty is diagnosed as being due to the standard assumption that capital for inventory is borrowed and hence boundless. We present a new analysis of inventory reduction decisions, such as adopting JIT replenishment or component substitution, using a deterministic batch sizing model which assumes that inventory is financed by the investors in the company and is thus finite. As a consequence, the investment level is treated as an additional variable of the decision analysis. Using the well established technique of constrained optimisation it is shown that for investor-financed operations the effective value of money invested in inventory is the marginal return on investment of the company, and increases with the degree of constraint. Thus, JIT policy options are especially favourable when low levels of inventory investment are sought, even without setup cost reduction, because the capital formerly invested in stock holdings of the JIT components can be reinvested in the inventory of other components to make their replenishment more efficient using larger batch sizes. The analysis is illustrated using an actual case study of a small manufacturing enterprise seeking to reduce inventory and increase return on investment. The analysis has interesting practical implications for inventory managers including a proposed simple method for identifying candidate components for JIT replenishment.     

On the distributions of infinite server queues with batch arrivals

Queues that feature multiple entities arriving simultaneously are among the oldest models in queueing theory, and are often referred to as “batch” (or, in some cases, “bulk”) arrival queueing systems. In this work, we study the effect of batch arrivals on infinite server queues. We assume that the arrival epochs occur according to a Poisson process, with treatment of both stationary and non-stationary arrival rates. We consider both exponentially and generally distributed service durations, and we analyze both fixed and random arrival batch sizes. In addition to deriving the transient mean, variance, and moment-generating function for time-varying arrival rates, we also find that the steady-state distribution of the queue is equivalent to the sum of scaled Poisson random variables with rates proportional to the order statistics of its service distribution. We do so through viewing the batch arrival system as a collection of correlated sub-queues. Furthermore, we investigate the limiting behavior of the process through a batch scaling of the queue and through fluid and diffusion limits of the arrival rate. In the course of our analysis, we make important connections between our model and the harmonic numbers, generalized Hermite distributions, and truncated polylogarithms.

     

Scheduling with batch setup times and earliness-tardiness penalties

We consider a scheduling model in which several batches of jobs need to be processed by a single machine. During processing, a setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. All the jobs in the same batch have a common due date that is either externally given as an input data or internally determined as a decision variable. Two problems are investigated. One problem is to minimize the total earliness and tardiness penalties provided that each due date is externally given. We show that this problem is NP-hard even when there are only two batches of jobs and the two due dates are unrestrictively large. The other problem is to minimize the total earliness and tardiness penalties plus the total due date penalty provided that each due date is a decision variable. We give some optimality properties for this problem with the general case and propose a polynomial dynamic programming algorithm for solving this problem with two batches of jobs. We also consider a special case for both of the problems when the common due dates for different batches are all equal. Under this special case, we give a dynamic programming algorithm for solving the first problem with an unrestrictively large due date and for solving the second problem. This algorithm has a running time polynomial in the number of jobs but exponential in the number of batches.     

Optimal investment in setup reduction in manufacturing systems with WIP inventories

A number of models have been proposed to predict optimal setup times, or optimal investment in setup reduction, in manufacturing cells. These have been based on the economic order quantity (EOQ) or economic production quantity (EPQ) model formulation, and have a common limitation in that they neglect work-in-process (WIP) inventories, which can be substantial in manufacturing systems. In this paper a new model is developed that predicts optimal production batch sizes and investments in setup reduction. This model is based on queuing theory, which permits it to estimate WIP levels as a function of the decisions variables, batch size and setup time. Optimal values for batch size and setup time are found analytically, even though the total cost model was shown to be strictly non-convex.     

Newsvendor-type models with decision-dependent uncertainty

Models for decision-making under uncertainty use probability distributions to represent variables whose values are unknown when the decisions are to be made. Often the distributions are estimated with observed data. Sometimes these variables depend on the decisions but the dependence is ignored in the decision maker??s model, that is, the decision maker models these variables as having an exogenous probability distribution independent of the decisions, whereas the probability distribution of the variables actually depend on the decisions. It has been shown in the context of revenue management problems that such modeling error can lead to systematic deterioration of decisions as the decision maker attempts to refine the estimates with observed data. Many questions remain to be addressed. Motivated by the revenue management, newsvendor, and a number of other problems, we consider a setting in which the optimal decision for the decision maker??s model is given by a particular quantile of the estimated distribution, and the empirical distribution is used as estimator. We give conditions under which the estimation and control process converges, and show that although in the limit the decision maker??s model appears to be consistent with the observed data, the modeling error can cause the limit decisions to be arbitrarily bad.     

Single-machine common due window assignment and scheduling to minimize the total cost

In this paper we consider a single-machine common due window assignment and scheduling problem with batch delivery cost. The starting time and size of the due window are decision variables. Finished jobs are delivered in batches. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find a job sequence, a delivery date for each job, and a starting time and a size for the due window that jointly minimize the total cost comprising earliness, weighted number of tardy jobs, job holding, due window starting time and size, and batch delivery. We provide some properties of the optimal solution and present polynomial-time algorithms for the problem.     

Batching deteriorating items with applications in computer communication and reverse logistics

We study two deterministic scheduling problems that combine batching and deterioration features. In both problems, there is a certain demand for identical good quality items to be produced in batches. In the first problem, each batch is assigned an individual machine that requires a cost and a time to be activated. All the machines are identical, work in parallel, and always produce good quality items. All the items are available at time zero and they deteriorate while waiting for production. Deterioration results in a linear increase of time and cost of production. In the second problem, there is a single machine that produces good quality as well as defective items in batches. Each batch is preceded by a setup time and requires a setup cost. Defective items have to be reworked on the same machine. They deteriorate while waiting for rework. At a time to be decided, the machine switches from production to rework defective items of the current batch. After rework, every defective item has the required good quality. In both problems, the objective is to find batch partitioning such that a linear combination of the production cost and production completion time is minimized. The two problems are observed at computer service providers and also reverse logistics. In computer service providers, machines and items correspond to communication service channels and information transfer tasks, respectively. We reduce both problems to minimizing a function of one variable representing the number of batches. In an optimal solution of either problem, there are at most two different batch sizes. Linear time algorithms are proposed for both problems.     

并行分批排序综述

并行分批排序起源于半导体芯片制造过程。在并行分批排序中,工件可成批加工,批加工机器最多可同时加工B个工件,批的加工时间为批中所有工件的最大工时。首先根据传统的机器环境和目标函数对并行分批排序已有成果进行分类介绍,主要为单机和平行机的机器环境,以及极小化最大完工时间、极小化总完工时间、极小化最大延迟、极小化误工工件数、极小化总延误和极小化最大延误的目标函数;然后梳理了由基本问题所衍生出来的具有新特点的16类新型并行分批排序,包括差异尺寸工件、多目标、工件加工时间或顺序存在限制、考虑费用和具有特殊机制等情况;最后展望未来的研究方向。     

A simple Tabu Search method to solve the mixed-integer linear bilevel programming problem

Multilevel programming is characterized as mathematical programming to solve decentralized planning problems. The models partition control over decision variables among ordered levels within a hierarchical planning structure of which the linear bilevel form is a special case of a multilevel programming problem. In a system with such a hierarchical structure, the high-level decision making situations generally require inclusion of zero-one variables representing ‘yes-no’ decisions. We provide a mixed-integer linear bilevel programming formulation in which zero-one decision variables are controlled by a high-level decision maker and real-value decision variables are controlled by a low-level decision maker. An algorithm based on the short term memory component of Tabu Search, called Simple Tabu Search, is developed to solve the problem, and two supplementary procedures are proposed that provide variations of the algorithm. Computational results disclose that our approach is effective in terms of both solution quality and efficiency.     

Progressive hedging innovations for a class of stochastic mixed-integer resource allocation problems

Numerous planning problems can be formulated as multi-stage stochastic programs and many possess key discrete (integer) decision variables in one or more of the stages. Progressive hedging (PH) is a scenario-based decomposition technique that can be leveraged to solve such problems. Originally devised for problems possessing only continuous variables, PH has been successfully applied as a heuristic to solve multi-stage stochastic programs with integer variables. However, a variety of critical issues arise in practice when implementing PH for the discrete case, especially in the context of very difficult or large-scale mixed-integer problems. Failure to address these issues properly results in either non-convergence of the heuristic or unacceptably long run-times. We investigate these issues and describe algorithmic innovations in the context of a broad class of scenario-based resource allocation problem in which decision variables represent resources available at a cost and constraints enforce the need for sufficient combinations of resources. The necessity and efficacy of our techniques is empirically assessed on a two-stage stochastic network flow problem with integer variables in both stages.     

Scheduling products with subassemblies and changeover time

We revisit the problem, previously studied by Coffman et al, of scheduling products with two subassemblies on a common resource, where changeovers consume time, under the objective of flow-time minimization. We derive some previously unidentified structural properties that could be important to researchers working on similar batch scheduling problems. We show that there exists a series of base schedules from which optimal schedules can be easily derived. As these base schedules build on each other, they are easy to construct as well. We also show that the structure of these base schedules is such that batch sizes decrease over time in a well-defined manner. These insights about the general form of the schedules might also be important to practitioners wanting some intuition about the schedule structure that they are implementing.