Dynamic Programming Algorithms for Generating Optimal Strip Layouts

This paper presents dynamic programming algorithms for generating optimal strip layouts of equal blanks processed by shearing and punching. The shearing and punching process includes two stages. The sheet is cut into strips using orthogonal guillotine cuts at the first stage. The blanks are punched from the strips at the second stage. The algorithms are applicable in solving the unconstrained problem where the blank demand is unconstrained, the constrained problem where the demand is exact, the unconstrained problem with blade length constraint, and the constrained problem with blade length constraint. When the sheet length is longer than the blade length of the guillotine shear used, the dynamic programming algorithm is applied to generate optimal layouts on segments of lengths not longer than the blade length, and the knapsack algorithm is employed to find the optimal layout of the segments on the sheet. Experimental computations show that the algorithms are efficient.     

Heuristic for constrained two-dimensional three-staged patterns

Three-staged cutting patterns are often used in dividing large plates into small rectangular items. Vertical cuts separate the plate into segments in the first stage, horizontal cuts split each segment into strips in the second stage, and vertical cuts divide each strip into items in the third stage. A heuristic algorithm for generating constrained three-staged patterns is presented in this paper. The optimization objective is to maximize the pattern value that is the total value of the included items, while the frequency of each item type should not exceed the specified upper bound. The algorithm uses an exact procedure to generate strips and two heuristic procedures to generate segments and the pattern. The pattern-generation procedure first determines an initial solution and then uses its information to generate more segments to extend the solution space. Computational results show that the algorithm is effective in improving solution quality.     

T-shape homogenous block patterns for the two-dimensional cutting problem

This paper presents an algorithm for unconstrained T-shape homogenous block cutting patterns of rectangular pieces. A vertical cut divides the stock sheet into two segments. Each segment consists of sections that have the same length and direction. A section contains a row of homogenous blocks. A homogenous block consists of homogenous strips of the same piece type. Each cut on the block produces just one strip. The directions of two strips cut successively from a block are either parallel or orthogonal. The algorithm uses a dynamic programming recursion to generate optimal blocks, solves knapsack problems to obtain the block layouts on the sections and the section layout on segments of various lengths, and optimally selects two segments to compose the cutting pattern. The computational results indicate that the algorithm is efficient in improving material usage, and the computation time is reasonable.     

A new dynamic programming procedure for three-staged cutting patterns

Three-staged patterns are often used to solve the 2D cutting stock problem of rectangular items. They can be divided into items in three stages: Vertical cuts divide the plate into segments; then horizontal cuts divide the segments into strips, and finally vertical cuts divide the strips into items. An algorithm for unconstrained three-staged patterns is presented, where a set of rectangular item types are packed into the plate so as to maximize the pattern value, and there is no constraint on the frequencies of each item type. It can be used jointly with the linear programming approach to solve the cutting stock problem. The algorithm solves three large knapsack problems to obtain the optimal pattern: One for the item layout on the widest strip, one for the strip layout on the longest segment, and the third for the segment layout on the plate. The computational results indicate that the algorithm is efficient.     

Generating optimal multi-segment cutting patterns for circular blanks in the manufacturing of electric motors

The author presents a method to generate optimal multi-segment cutting patterns to improve the material usage of the circular blanks in the manufacturing of rotors and stators of electric motors. In the patterns generated, the sheet is divided into segments with cut lines perpendicular to the sheet length. The width of the segments equals to the sheet width. The lengths of the segments may be different. A segment includes one or more strips that are parallel to the sheet length. More than one row of identical blanks can appear in a strip. The method applies the property of the optimal patterns to reduce the number of segment lengths that should be considered. It uses the knapsack algorithm to determine the optimal arrangement of blanks on each segment and the numbers of the segment lengths in the sheet to make the material usage reach its maximum. The computational results indicate that the method is efficient both in computation time and in material usage. The solution to an example is given.     

Fast heuristic for constrained homogenous T-shape cutting patterns

Homogenous T-shape (HTS) cutting patterns are welcomed when the two-phase process is used to produce rectangular pieces from the stock plate, where the plate is cut into homogenous strips at the first phase, and the strips are divided into pieces at the second phase. A heuristic is presented for generating constrained HTS patterns, where the objective is to maximize the pattern value that is equal to the total value of the included pieces, observing the upper bound constraint on the frequency of each piece type. The heuristic is based on dynamic programming and branch-and-bound techniques. It can yield solutions close to optimal with short computation time. By providing good initial solutions, the heuristic can greatly improve the time efficiency of an existing exact branch-and-bound algorithm.     

Improved heuristics for the minimum weight triangulation problem

Given a planar point setS, a triangulation ofS is a maximal set of non-intersecting line segments connecting the points. The minimum weight triangulation problem is to find a triangulation ofS such that the sum of the lengths of the line segments in it is the smallest. No polynomial time algorithm is known to produce the optimal or even a constant approximation of the optimal solution, and it is also unknown whether the problem is NP-hard. In this paper, we propose two improved heuristics, which triangulate a set ofn points in a plane inO(n ³) time and never do worse than the minimum spanning tree triangulation algorithm given by Lingas and the greedy spanning tree triangulation algorithm given by Heath and Pemmaraju. These two algorithms both produce an optimal triangulation if the points are the vertices of a convex polygon, and also do the same in some special cases.     

A four-input three-stage queuing network approach to model an industrial system

An industrial system is represented as a four-input, three-stage queuing network in this paper. The four-input queuing network receives orders from clients, and the orders are waiting to be served. Each order comprises (i) time of occurrence of the orders, and (ii) quantity of items to be delivered in each order. The objective of this paper is to compute the optimal path which produces the least response time for the delivery of items to the final destination along the three stages of the network. The average number of items that can be delivered with this minimum response time constitute the optimum capacity of the queuing network. After getting serviced by the last node (a queue and its server) in each stage of the queuing network, a decision is made to route the items to the appropriate node in the next stage which can produce the least response time. Performance measures such as average queue lengths, average response times, average waiting times of the jobs in the four-input network are derived and plotted. Closed-form expressions for the equivalent service rate, equivalent average queue lengths, equivalent response and waiting times of a single equivalent queue with a server representing the entire four-input queuing network are also derived and plotted.     

An elementary algorithm for reporting intersections of red/blue curve segments

Let E_r and E_b be two sets of x-monotone and non-intersecting curve segments, E=E_rE_b and |E|=n. We give a new sweep-line algorithm that reports the k intersecting pairs of segments of E. Our algorithm uses only three simple predicates that allow to decide if two segments intersect, if a point is left or right to another point, and if a point is above, below or on a segment. These three predicates seem to be the simplest predicates that lead to subquadratic algorithms. Our algorithm is almost optimal in this restricted model of computation. Its time complexity is O(nlogn+kloglogn) and it requires O(n) space.     

Dynamic programming algorithms for the optimal cutting of equal rectangles

This paper presents dynamic programming algorithms for generating optimal guillotine-cutting patterns of equal rectangles. The algorithms are applicable for solving the unconstrained problem where the blank demand is unconstrained, the constrained problem where the demand is exact, the unconstrained problem with blade length constraint, and the constrained problem with blade length constraint. The algorithms are able to generate the simplest optimal patterns to simplify the cutting process. When the sheet length is longer than the blade length of the guillotine shear used, the dynamic programming algorithm is applied to generate optimal layouts on segments of lengths no longer than the blade length, and the knapsack algorithm is employed to find the optimal layout of the segments on the sheet. The computational results indicate that the algorithms presented are more efficient than the branch-and-bound algorithms, which are the best algorithms so far that can guarantee the simplest patterns.     

Mining time series data for segmentation by using Ant Colony Optimization

In trying to distinguish data features within time series data for specific time intervals, time series segmentation technology is often required. This research divides time series data into segments of varying lengths. A time series segmentation algorithm based on the Ant Colony Optimization (ACO) algorithm is proposed to exhibit the changeability of the time series data. In order to verify the effect of the proposed algorithm, we experiment with the Bottom-Up method, which has been reported in available literature to give good results for time series segmentation. Simulation data and genuine stock price data are also used in some of our experiments. The research result shows that time series segmentation run by the ACO algorithm not only automatically identifies the number of segments, but its segmentation cost was lower than that of the time series segmentation using the Bottom-Up method. More importantly, during the ACO algorithm process, the degree of data loss is also less compared to that of the Bottom-Up method.     

Finding the optimal CSP inventory level for multi-echelon system in Air Force using random effects regression model

Determining the optimal inventory level of CSP (concurrent spare parts) is crucial at the time of acquisition of new aircrafts. Most of the existing optimal CSP models do not take into account the time varying characteristics of CSP even though their demand rates are sensitive to such variation. In this paper, we introduce the CSP inventory model using a two stage approach. At the first stage, we use a random effects model to predict the expected demand of CSP in a multi-echelon system consisting of depot and bases based on CSPs varying characteristics with time. At the second stage, we find the optimal inventory level of CSP by using the optimization algorithm with various constraints under limited budget. The study is expected to contribute to the Air Force establishing the optimal national defense procurement policy for CSP of aircrafts.     

A fast solution method for the time-dependent orienteering problem

This paper introduces a fast solution procedure to solve 100-node instances of the time-dependent orienteering problem (TD-OP) within a few seconds of computation time. Orienteering problems occur in logistic situations were an optimal combination of locations needs to be selected and the routing between the selected locations needs to be optimized. In the time-dependent variant, the travel time between two locations depends on the departure time at the first location. Next to a mathematical formulation of the TD-OP, the main contribution of this paper is the design of a fast and effective algorithm to tackle this problem. This algorithm combines the principles of an ant colony system (ACS) with a time-dependent local search procedure equipped with a local evaluation metric. Additionally, realistic benchmark instances with varying size and properties are constructed. The average score gap with the known optimal solution on these test instances is only 1.4% with an average computation time of 0.5 seconds. An extensive sensitivity analysis shows that the performance of the algorithm is insensitive to small changes in its parameter settings.     

Timetabling optimization of a single railway track line with sensitivity analysis

The paper deals with the timetabling problem of a single-track railway line. To solve the timetabling problem, we propose a three-stage approach combining several optimization criteria. Initially and mainly, the maximum relative travel time (ratio of travel time to minimum possible travel time) is minimized subject to a set of constraints, including departure time, train speed, minimum and maximum dwell time, and headway at track segments and stations. Since this problem has many solutions, the process is repeated for other trains, keeping the relative travel times of the critical train fixed, until all trains have been assigned their optimal relative travel times. In the second stage, the prompt allocation of trains is a secondary objective, and finally, in the third stage, the one minimizing the sum of the station dwell times of all trains, keeping the relative travel times constant, is selected to reduce fuel consumption, as a tertiary objective. To consider the user preferences in the optimization problems, the user preference departure time is used instead of the actual planned departure times. In order to guarantee that the exact or a very good approximate global optimum is attained, an algorithm based on the bisection rule is used. This method allows the computation time to be reduced in at least one order of magnitude for 42 trains. The problem of sensitivity analysis is also discussed, and closed form formulas for the sensitivities in terms of the dual variables are given. Several examples of applications are presented to illustrate the goodness of the proposed method. The results show that an adequate selection of intermediate stations and of the departure times are crucial in the good performance of the line and that inadequate spacings between consecutive trains can block the line. In addition, it is shown that, in order to improve performance, regional trains must be scheduled just ahead of or following the long distance trains, rather than having independent schedules. The sensitivities are shown to be very useful in identifying critical trains, segments, stations, departure times, and headways and in suggesting line infrastructure changes.     

Lot streaming for quality control in two-stage batch production

We consider a two-stage batch manufacturing process in which the first stage shifts out-of-control at iid exponential times after starting in control. To improve quality, a production batch at Stage 1 is subjected to lot streaming: it is divided into sublots that are processed at Stage 1 and then passed one-by-one to Stage 2 for simultaneous inspection and processing. In any sublot, Stage 1 produces good items before the shift and bad items after. The state of Stage 1 is known as soon as a bad item is encountered in Stage 2, at which time Stage 1 is re-set to the in-control state. We examine both cases of continuous first-stage and continuous second-stage production. For each case we examine both LIFO and FIFO inspection and processing policies at Stage 2. We use nonlinear programming to develop lot streaming policies which minimize the expected number of defective items for LIFO and FIFO policies. We also develop simple approximately optimal policies and compare the output performance of optimal, approximately optimal and equal-lot policies (when applicable) in a numerical example.     

A sequential multiple change-point detection procedure via VIF regression

In this paper, we propose a procedure for detecting multiple change-points in a mean-shift model, where the number of change-points is allowed to increase with the sample size. A theoretic justification for our new method is also given. We first convert the change-point problem into a variable selection problem by partitioning the data sequence into several segments. Then, we apply a modified variance inflation factor regression algorithm to each segment in sequential order. When a segment that is suspected of containing a change-point is found, we use a weighted cumulative sum to test if there is indeed a change-point in this segment. The proposed procedure is implemented in an algorithm which, compared to two popular methods via simulation studies, demonstrates satisfactory performance in terms of accuracy, stability and computation time. Finally, we apply our new algorithm to analyze two real data examples.     

基于信用支付和现金折扣的变质物品库存模型

本文在供应商提供给零售商定期信用支付和现金折扣情况下,研究了零售商的变质物品最优库存问题。基于信用支付和现金折扣的两种支付条件下,分四种情况建立库存模型,并给出了寻求变质物品最优订购周期和最优付款时间的有效算法。最后,给出算例以及最优解,以说明本模型及求解过程。     

An inventory model of deteriorating items with lot-size dependent replenishment cost and a linear trend in demand

This paper presents an inventory model for deteriorating items over a finite time horizon where the demand increases linearly with time. The method is developed by assuming that the successive replenishment cycle lengths are the same. Many O.R. scientists/researchers obtained an optimal replenishment schedule where the replenishment cost is constant in each cycle length over the finite time horizon. In this paper, we relax the assumption of fixed replenishment cost. The replenishment cost per replenishment is taken to be linearly dependent on the lot-size of that replenishment. Shortages are allowed and are fully backlogged. As a special case, the results for the model without shortages are derived. Finally, two numerical examples are presented to illustrate the model.     

Optimal appointment scheduling in continuous time: The lag order approximation method

We study appointment scheduling problems in continuous time. A finite number of clients are scheduled such that a function of the waiting time of clients, the idle time of the server, and the lateness of the schedule is minimized. The optimal schedule is notoriously hard to derive within reasonable computation times. Therefore, we develop the lag order approximation method, that sets the client’s optimal appointment time based on only a part of his predecessors. We show that a lag order of two, i.e., taking two predecessors into account, results in nearly optimal schedules within reasonable computation times. We illustrate our approximation method with an appointment scheduling problem in a CT-scan area.     

A recursive algorithm for constrained two-dimensional cutting problems

This paper presents a recursive algorithm for constrained two-dimensional guillotine cutting problems of rectangular items. The algorithm divides a stock plate into a sequence of small rectangular blocks. For the current block considered, it selects an item, puts it at the left-bottom corner of the block, and determines the direction of the dividing cut that divides the unoccupied region of the block into two smaller blocks for further consideration. The dividing cut is either along the upper edge or along the right edge of the selected item. The upper bound obtained from the unconstrained solution is used to shorten the searching space. The computational results on benchmark problems indicate that the algorithm can improve the solutions, and is faster than other algorithms.