Batch sizing and job sequencing on a single machine

We study a single-machine scheduling problem in which the items to be processed have to be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between consecutive batches. For any fixed, but arbitrary item sequence, we present an algorithm that finds a sequence of batches such that the total flow time of the items is minimized; we prove that for a set ofn items, the algorithm runs inO(n) time. We show that, among all sequences, the one leading to the minimum flow time has the items in non-decreasing order of running times. Thus, the optimal algorithm for the combined problem, called thebatch-sizing problem, runs inO(n logn) time. We also prove that this algorithm yields an improved solution to a scheduling problem recently studied by Baker [1].     

Optimal replacement policy for multicomponent systems: An application to a dairy herd

We consider the problem of finding an optimal replacement policy for a system which has many components. The main difficulty in this problem is that there is an interaction among the items in the system. Thus, the optimal replacement decision for each item depends not only on its state, but also on those of the other items in the systems. This interaction is due to the the fact that the both the stock size and the supply of replacement items is limited. (Instead of an unlimited supply of standard replacement items as is implicitly assumed by most of the replacement models). In our application to dairy herd managenent the problem is further complicated by the fact that this limited supply is not exogenous to the process but is actually generated by it. This is due to the fact that almost all the replacement young cows are home grown. The traits of these young cows have genetic dependence on those of their parents. The dairy herd management problem is actually a special case of the joint replacement and inventory problem, where the groups of cows are the stock of replacement items. At each point of time the decision problem is to find the optimal composition of items from the available population of items. An exact derivation of the optimal replacement policy for such problems is very complicated because the optimal decisions for each period depends on the state of the whole stock, and of all the available replacement components. This leads to a dynamic programming problem with a very large number of state variables which is not feasible to solve numerically due to the great amount of computer time involved.This paper presents a practical method for obtaining an approximate solution for the above described problem. The computational difficulty caused by the tremendously large dimensionality of the state variable is overcome by means of an iterative method which combines simulation and Dynamic Programming approach to compute successive linear approximations of the value function.     

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.     

Multi-product lot-sizing and sequencing on a single imperfect machine

A problem of lot-sizing and sequencing several products on a single machine is studied. The machine is imperfect in two senses: it can produce defective items and it can breakdown. The number of defective items for each product is given as an integer valued non-decreasing function of the manufactured quantity. The total machine breakdown time is given as a real valued non-decreasing function of the manufactured quantities of all the products. A sequence-dependent setup time is required to switch the machine from manufacturing one product to another. Two problem settings are considered. In the first, the objective is to minimize the completion time of the last item, provided that all the product demands for the good quality items are satisfied. In the second, the goal is to minimize the total cost of demand dissatisfaction, subject to an assumption that the completion time of the last item does not exceed a given upper bound. Computational complexity and algorithmic results are presented, including an FPTAS for a special case of the cost minimization problem, and computer experiments with the FPTAS.     

网上分批拍卖中的保留价比较分析

本文以Onsale网上拍卖公司的拍卖方式为背景,研究了在给定拍卖时间长度与拍卖总供给量的条件下,将拍卖品分若干批拍卖这一问题.建立了其马尔可夫决策过程模型,分别在公开保留价与不公开保留价的两种情况下,研究了每批拍卖品数量的最优问题,并证明了网上拍卖中商家不公开保留价时获得的最大期望利润多于公开时的最大期望利润.     

Batch scheduling of deteriorating reworkables

The problem of scheduling the production of new and recoverable defective items of the same product manufactured on the same facility is studied. Items are processed in batches. Each batch comprises two sub-batches processed consecutively. In the first sub-batch, all the items are newly manufactured. Some of them are of the required good quality and some are defective. The defective items are remanufactured in the second sub-batch. They deteriorate while waiting for rework. This results in increased time and cost for their remanufacturing. All the items in the same sub-batch complete at the same time, which is the completion time of the last item in the sub-batch. Each remanufactured defective item is of the required good quality. It is assumed that the percentage of defective items in each batch is the same. A setup time is required to start batch processing and to switch from manufacturing to remanufacturing. The demands for good quality items over time are given. The objective is to find batch sizes such that the total setup and inventory holding cost is minimized and all the demands are satisfied. Dynamic programming algorithms are presented for the general problem and some important special cases.     

Heuristic and Exact Algorithms for the Precedence-Constrained Knapsack Problem

The knapsack problem (KP) is generalized taking into account a precedence relation between items. Such a relation can be represented by means of a directed acyclic graph, where nodes correspond to items in a one-to-one way. As in ordinary KPs, each item is associated with profit and weight, the knapsack has a fixed capacity, and the problem is to determine the set of items to be included in the knapsack. However, each item can be adopted only when all of its predecessors have been included in the knapsack. The knapsack problem with such an additional set of constraints is referred to as the precedence-constrained knapsack problem (PCKP). We present some dynamic programming algorithms that can solve small PCKPs to optimality, as well as a preprocessing method to reduce the size of the problem. Combining these, we are able to solve PCKPs with up to 2000 items in less than a few minutes of CPU time.     

Decision making and card collecting

^** D.K.Smith{at}exeter.ac.uk Collecting a set of different, yet similar, items is a popularhobby. The "coupon collector's problem" is concerned with thenumber of items which must be obtained, one at a time, in orderto complete the set, assuming that the collector is samplingfrom an infinite population where each item has a known probabilityof being found. In recent years, manufacturers have chosen toproduce the items in sealed packets which contain more thanone item, and possibly items from more than one set. This paperconsiders the problem of collecting items in packets, and thedecision problem faced by a collector who is offered the chanceto buy several packets at a discount. Dynamic programming isused to determine when it is worthwhile to purchase in bulk,for various sets and packets, as a function of the discountrate. Finally, mention is made of the other player in the transaction,the card manufacturer, who is also a decision-maker.     

Bin packing with general cost structures

Following the work of Anily et?al., we consider a variant of bin packing called bin packing with general cost structures (GCBP) and design an asymptotic fully polynomial time approximation scheme (AFPTAS) for this problem. In the classic bin packing problem, a set of one-dimensional items is to be assigned to subsets of total size at most 1, that is, to be packed into unit sized bins. However, in GCBP, the cost of a bin is not 1 as in classic bin packing, but it is a non-decreasing and concave function of the number of items packed in it, where the cost of an empty bin is zero. The construction of the AFPTAS requires novel techniques for dealing with small items, which are developed in this work. In addition, we develop a fast approximation algorithm which acts identically for all non-decreasing and concave functions, and has an asymptotic approximation ratio of 1.5 for all functions simultaneously.     

Optimum Redundancy with Equipment that Operates and Idles

Despite their widespread exclusion from the literature on reliability and replacement, many items of equipment are subject to failures to idle as well as failures to operate. For such equipment a new optimisation problem arises at the stage of systems design in terms of the optimal use of redundancy to maximise expected systems life. The models hitherto used as the basis for the solution of this optimization problem ignore the dependence that should exist for the solutions upon the operating and idling requirements to which the system is to be exposed. In this paper a simple model for equipment subject to such opposite failure modes is constructed which takes explicit account of the proportion of time the equipment is in use. The implications of this new model for the selection of an optimum redundancy configuration are illustrated for the case where four identical items of equipment are available.     

An optimal stocking problem to minimize the expected time to sellout

We consider an assortment planning problem where the objective is to minimize the expected time to sell all items in the assortment. We provide several structural results for the optimal assortment. We present a heuristic policy, which we prove is asymptotically optimal. We also show that there are alternate objective criteria under which the problem simplifies considerably.     

Stock replenishment policies for a stochastic exponentially-declining demand process

This paper addresses the problem of determining stock replenishment policies to meet the demand for spare parts for items of equipment which are no longer manufactured. The assumptions that the number of items still in use is decreasing and that parts fail randomly lend credence to a Poisson demand process with an underlying mean which is decreasing exponentially. We use a dynamic programming formulation in continuous time to determine that replenishment policy which minimises the mean total discounted cost of set-up/order, unit production/purchase, unsatisfied demand and stock left over at the end of the time horizon.     

Reoptimizing the 0-1 knapsack problem

In this paper we study the problem where an optimal solution of a knapsack problem on n items is known and a very small number k of new items arrive. The objective is to find an optimal solution of the knapsack problem with n+k items, given an optimal solution on the n items (reoptimization of the knapsack problem). We show that this problem, even in the case k=1, is NP-hard and that, in order to have effective heuristics, it is necessary to consider not only the items included in the previously optimal solution and the new items, but also the discarded items. Then, we design a general algorithm that makes use, for the solution of a subproblem, of an α-approximation algorithm known for the knapsack problem. We prove that this algorithm has a worst-case performance bound of , which is always greater than α, and therefore that this algorithm always outperforms the corresponding α-approximation algorithm applied from scratch on the n+k items. We show that this bound is tight when the classical Ext-Greedy algorithm and the algorithm are used to solve the subproblem. We also show that there exist classes of instances on which the running time of the reoptimization algorithm is smaller than the running time of an equivalent PTAS and FPTAS.     

Tree search for the stacking problem

The stacking problem is a hard combinatorial optimization problem with high practical interest in, for example, steel storage or container port operations. In this problem, a set of items is stored in a warehouse for a period of time, and a crane is used to place them in a limited number of stacks. Since the entrance and exit of items occurs in an arbitrary order, items may have to be relocated in order to reach and deliver other items below them. The objective of the problem is to find a feasible sequence of movements that delivers all items, while minimizing the total number of movements. We study the scalability of an exact approach to this problem, and propose two heuristic methods to solve it approximately. The two heuristic approaches are a multiple simulation algorithm using semi-greedy construction heuristics, and a stochastic best-first tree search algorithm. The two methods are compared in a set of challenging instances, revealing a superior performance of the tree search approach in most cases.     

Double optimal stopping times and dynamic pricing problem: description of the mathematical model

In many industries, managers face the problem of selling a given stock of items by a deadline. We investigate the problem of dynamically pricing such inventories when demand is price sensitive and stochastic and the firm’s objective is to maximize expected revenues. Examples that fit this framework include retailers selling fashion and seasonal goods and the travel and leisure industry, which markets space such as seats on airline flights, cabins on vacation cruises, hotels renting rooms before midnight and theaters selling seats before curtain time that become worthless if not sold by a specific time. Given a fixed number of seats, rooms, or coats, the objective for these industries is to maximize revenues in excess of salvage value. When demand is price sensitive and stochastic, pricing is an effective tool to maximize revenues. In this paper, we address the problem of deciding the optimal timing of a double price changes from a given initial price to given lower or higher prices. Under mild conditions, it is shown that it is optimal to decrease the initial price as soon as the time-to-go falls below a time threshold and increase the price if time-to-go is longer than adequate time threshold. These thresholds depend on the number of yet unsold items.      

Exploiting locality: approximating sorting buffers

The sorting buffers problem is motivated by many applications in manufacturing processes and computer science, among them car-painting and file servers architecture. The input is a sequence of items of various types. All the items must be processed, one by one, by a service station. We are given a random-access sorting buffer with a limited capacity. Whenever a new item arrives it may be moved directly to the service station or stored in the buffer. Also, at any time items can be removed from the buffer and assigned to the service station. Our goal is to give the service station a sequence of items with minimum type transitions. We generalize the problem to allow items with different sizes and type transitions with different costs. We give a polynomial-time 9-approximation algorithm for the maximization variant of this problem, which improves the best previously known 20-approximation algorithm.     

Calculator Use on NAEP: A Look at Fourth‐ and Eighth‐Grade Mathematics Achievement

This article summarizes research conducted on calculator block items from the 2007 fourth‐ and eighth‐grade National Assessment of Educational Progress Main Mathematics. Calculator items from the assessment were categorized into two categories: problem‐solving items and noncomputational mathematics concept items. A calculator has the potential to be used as a problem‐solving tool for items categorized in the first category. On the other hand, there are no practical uses for calculators for noncomputational mathematics concept items. Item‐level performance data were disaggregated by student‐reported calculator use to investigate the differences in achievement of those fourth‐ and eighth‐grade students who chose to use calculators versus those who did not, and whether or not the nation's fourth and eighth graders are able to identify items where calculator use serves as an aide for solving a given mathematical problem. Results from the analysis show that eighth graders, in particular, benefit most from the use of calculators on problem‐solving items. A small percentage of students at both grade levels attempted to use a calculator to solve problems in the noncomputational mathematics concept category (items in which the use of a calculator does not serve as a tool to solve the problem).     

A mathematical programming system for preference and compatibility maximized menu planning and scheduling

In this paper, the analytical representation of food preference is used in a separable non-linear program to yield the serving frequencies of menu items for a finite time horizon. The frequencies obtained in this way insure cost and nutritional control. Subsequently, the scheduling problem dealing with item assignments to meals and days is formulated as an integer program consisting of several transportation problems linked by weekly nutritional constraints. This problem is solved using a branch and bound algorithm which employs Lagrangian relaxation to obtain bounds and to decide on branching strategy.     

The constrained compartmentalized knapsack problem: mathematical models and solution methods

The constrained compartmentalized knapsack problem can be seen as an extension of the constrained knapsack problem. However, the items are grouped into different classes so that the overall knapsack has to be divided into compartments, and each compartment is loaded with items from the same class. Moreover, building a compartment incurs a fixed cost and a fixed loss of the capacity in the original knapsack, and the compartments are lower and upper bounded. The objective is to maximize the total value of the items loaded in the overall knapsack minus the cost of the compartments. This problem has been formulated as an integer non-linear program, and in this paper, we reformulate the non-linear model as an integer linear master problem with a large number of variables. Some heuristics based on the solution of the restricted master problem are investigated. A new and more compact integer linear model is also presented, which can be solved by a branch-and-bound commercial solver that found most of the optimal solutions for the constrained compartmentalized knapsack problem. On the other hand, heuristics provide good solutions with low computational effort.     

An agent-based approach to the two-dimensional guillotine bin packing problem

The two-dimensional guillotine bin packing problem consists of packing, without overlap, small rectangular items into the smallest number of large rectangular bins where items are obtained via guillotine cuts. This problem is solved using a new guillotine bottom left (GBL) constructive heuristic and its agent-based (A–B) implementation. GBL, which is sequential, successively packs items into a bin and creates a new bin every time it can no longer fit any unpacked item into the current one. A–B, which is pseudo-parallel, uses the simplest system of artificial life. This system consists of active agents dynamically interacting in real time to jointly fill the bins while each agent is driven by its own parameters, decision process, and fitness assessment. A–B is particularly fast and yields near-optimal solutions. Its modularity makes it easily adaptable to knapsack related problems.