The one-dimensional cutting stock problem with due dates

The one-dimensional cutting stock problem is the problem of cutting stock material into shorter lengths, in order to meet demand for these shorter lengths while minimizing waste. In industrial cutting operations, it may also be necessary to fill the orders for these shorter lengths before a given due date. We propose new optimization models and solution procedures which solve the cutting stock problem when orders have due dates. We evaluate our approach using data from a large manufacturer of reinforcement steel and show that we are able to solve industrial-size problems, while also addressing common cutting considerations such as aggregation of orders, multiple stock lengths and cutting different types of material on the same machine. In addition, we evaluate operational performance in terms of resulting waste and tardiness of orders using our model in a rolling horizon framework.     

An iterative sequential heuristic procedure to a real-life 1.5-dimensional cutting stock problem

This paper addresses a real-life 1.5D cutting stock problem, which arises in a make-to-order plastic company. The problem is to choose a subset from the set of stock rectangles to be used for cutting into a number of smaller rectangular pieces so as to minimize total production cost and meet orders. The total production cost includes not only material wastage, as in traditional cutting stock problems, but also production time. A variety of factors are taken into account, like cutter knife changes, machine restrictions, due dates and other work in progress limitations. These restrictions make the combinatorial structure of the problem more complex. As a result, existing algorithms and mathematical models are no longer appropriate. Thus we developed a new 1.5D cutting stock model with multiple objectives and multi-constraints and solve this problem in an incomplete enumerative way. The computational results show that the solution procedure is easy to implement and works very well.     

Cutting aluminium coils with high length variabilities

A case study of a cutting stock problem in an aluminium mill is presented. Orders have release dates, due dates, a total length and may be delivered in any number of coils, the length of the coils being bounded from below and above. A variety of different cutting machines is available, hierarchical cuts may be necessary to produce small widths. The mill is capable of producing custom-made coils within certain bounds but there is a declared preference for standard widths. The task is to group the orders into coils which can be produced by the mill and slit by the machines. Waste should be minimized, the dates should be obeyed, the load of the machines should be balanced. In spite of the fact that column generation is not possible, the problem is solved efficiently in practice by a multi-pattern approach using linear programming.     

考虑订单取件时间和柔性时间窗的取送货车辆路径问题

研究了同城配送中考虑订单取货时间和柔性时间窗的取送货车辆路径问题,考虑同城配送中订单起终点,订单取货时间和订单配送的柔性时间窗,车容量限制等因素。首先构建以配送成本与超时惩罚成本之和最小化为目标的混合整数线性模型。其次,设计了含多种有效不等式及其对应分离算法的改进分支切割算法对该模型进行精确求解。最后通过实验测试分析了不等式的性能,验证了算法的有效性,实验表明适当的减少车辆数和增大装载能力能够有效的减少成本。     

A decision support system for order acceptance/rejection in hybrid MTS/MTO production systems

In this paper, we present a novel decision support system for order acceptance/rejection in a hybrid Make-to-Stock/Make-to-Order production environment. The proposed decision support system is comprised of five steps. At the first step, the customers are prioritized based on a fuzzy TOPSIS method. Rough-cut capacity and rough-cut inventory are calculated in the second step and in case of unavailability in capacity and materials, some undesirable orders are rejected. Also, proper decisions are made about non-rejected orders. At the next step, prices and delivery dates of the non-rejected orders are determined by running a mixed-integer mathematical programming model. At the fourth step, a set of guidelines are proposed to help the organization negotiate over price and due date with the customers. In the next step, if the customer accepts the offered price and delivery date, the order is accepted and later considered in the production schedule of the shop floor, otherwise the order is rejected. Finally, numerical experiments are conducted to show the tractability of the applied mathematical programming model.     

On unit time open shops with additional restrictions

We consider open shop problems with unit processing times,n jobs have to be processed onm machines. The order in which a given job is processed on the machines is not fixed. For each job a release time or a due date may be given. Additional, we consider the restriction that every machine must perform all corresponding operations without any delay time. Unit time open shop problems with release times to minimize total completion time were unsolved up to now for both allowed and forbidden delay times. We will solve these problems in the case of two and three machines. Furthermore we will give polynomial algorithms for several no-delay-problems with due dates.     

On Dual Based Lower Bounds for the Sequential Ordering Problem with Precedences and Due Dates

The Sequential Ordering Problem (herewith, SOP) with precedence relationships was introduced in Escudero (1988), and extended to cover release and due dates in Escudero and Sciomachen (1993). It has a broad range of applications, mainly in production planning for manufacturing systems. The problem consists of finding a minimum weight Hamiltonian path on a directed graph with weights on the nodes and the arcs, satisfying precedence relationships among the nodes and given lower and upper bounds on the weights of the Hamiltonian subpaths. In this paper we present a model for the constrained minimum weight Hamiltonian path problem with precedences and due dates forcing constraints, and introduce related valid cuts that can be used in a separation framework for the dual (Lagrangian based) relaxation of the problem. We also provide an heuristic separation procedure to obtain those cuts, so-called the Lagrangian Relax-and-Cut (LRC) scheme. Computational experience is given for variations of some SOP cases already reported in the literature.     

A two-objective mathematical model without cutting patterns for one-dimensional assortment problems

This paper considers a one-dimensional cutting stock and assortment problem. One of the main difficulties in formulating and solving these kinds of problems is the use of the set of cutting patterns as a parameter set in the mathematical model. Since the total number of cutting patterns to be generated may be very huge, both the generation and the use of such a set lead to computational difficulties in solution process. The purpose of this paper is therefore to develop a mathematical model without the use of cutting patterns as model parameters. We propose a new, two-objective linear integer programming model in the form of simultaneous minimization of two contradicting objectives related to the total trim loss amount and the total number of different lengths of stock rolls to be maintained as inventory, in order to fulfill a given set of cutting orders. The model does not require pre-specification of cutting patterns. We suggest a special heuristic algorithm for solving the presented model. The superiority of both the mathematical model and the solution approach is demonstrated on test problems.     

Operational extended model formulations for Advanced Planning and Scheduling systems

Since the basic reasoning of Manufacturing Resources Planning (MRPII) systems is flawed, a new breed of concepts called Advanced Planning and Scheduling systems (APS) have recently emerged to overcome the problems occurring on the shop floor. In this study, we develop improved and extended mixed integer programming formulations for APS systems at the factory planning level. First, we develop a basic model which explicitly considers capacity constraints, operation sequences, processing times, and due dates in a multi-machine, multi-order, multi-item environment where an item can be processed on a given set of eligible machines. The extensions to the basic model include sequence dependent setups, and transfer times between machines. We also show that our model with a little modification could be used to quote delivery times for customer orders in case due dates are not specified. We provide numerical examples and our conclusions along with future research directions.     

Scheduling orders for multiple product types to minimize total weighted completion time

We consider the problem of scheduling orders for multiple different product types in an environment with m dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the m dedicated machines; that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number (?2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space.     

A branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to meet due dates

In most deterministic scheduling problems, job-processing times are regarded as constant and known in advance. However, in many realistic environments, job-processing times can be controlled by the allocation of a common resource to jobs. In this paper, we consider the problem of scheduling jobs with arbitrary release dates and due dates on a single machine, where job-processing times are controllable and are modeled by a non-linear convex resource consumption function. The objective is to determine simultaneously an optimal processing permutation as well as an optimal resource allocation, such that no job is completed later than its due date, and the total resource consumption is minimized. The problem is strongly NP\mathcal{NP}-hard. A branch and bound algorithm is presented to solve the problem. The computational experiments show that the algorithm can provide optimal solution for small-sized problems, and near-optimal solution for medium-sized problems in acceptable computing time.     

Scheduling with controllable release dates and processing times: Makespan minimization

The paper deals with the single-machine scheduling problem in which job processing times as well as release dates are controllable parameters and they may vary within given intervals. While all release dates have the same boundary values, the processing time intervals are arbitrary. It is assumed that the cost of compressing processing times and release dates from their initial values is a linear function of the compression amount. The objective is to minimize the makespan together with the total compression cost. We construct a reduction to the assignment problem for the case of equal release date compression costs and develop an O(n²) algorithm for the case of equal release date compression costs and equal processing time compression costs. For the bicriteria version of the latter problem with agreeable processing times, we suggest an O(n²) algorithm that constructs the breakpoints of the efficient frontier.     

Production scheduling with applications in the printing industry

This paper presents a technique for the solution of scheduling problems encountered in a printing company that can be applied to a range of practical industrial problems. The aim of the research was to develop a due date scheduling algorithm within the framework of the scheduling system already in use by the company. The objective was to enable jobs to be scheduled as close to their due dates as possible, while ensuring that the resultant schedule was feasible with respect to work centre capacities and earliest start date constraints.     

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.     

New model and heuristic solution approach for one-dimensional cutting stock problem with usable leftovers

In the one-dimensional cutting stock problem with usable leftovers (1DCSPUL), items of the current order are cut from stock bars to minimize material cost. Here, stock bars include both standard ones bought commercially and old leftovers generated in processing previous orders, and cutting patterns often include new leftovers that are usable in processing subsequent orders. Leftovers of the same length are considered to be of the same type. The number of types of leftovers should be limited to simplify the cutting process and reduce the storage area. This paper presents an integer programming model for the 1DCSPUL with limited leftover types and describes a heuristic algorithm based on a column-generation procedure to solve it. Computational results show that the proposed approach is more effective than several published algorithms in reducing trim loss, especially when the number of types of leftovers is limited.     

Minimizing the weighted number of tardy jobs on a single machine with release dates

In this paper, we describe an exact algorithm to minimize the weighted number of tardy jobs on a single machine with release dates. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple-choice knapsack provides the bounds. Extensive computational experiments indicate the proposed exact algorithm solves either weighted or unweighted problems. It solves the hardest problems to date. Indeed, it solves all previously unsolved instances. Its run time is the shortest to date.     

The Cutting Stock Problem in the Flat Glass Industry

The cutting stock problem occurs where large rectangles of some material require cutting into smaller rectangles, in the most appropriate way, to satisfy an order book. A linear programming approach to the problem has been suggested by P. C. Gilmore and R. E. Gomory. An application of this approach in the glass industry is described which is shown to be inadequate since it only satisfies a wastage criterion. In practice, multiple criteria must be satisfied and two alternative approaches using linear programming and heuristic scheduling are proposed.     

工作有到达时间且拒绝工件总个数受限的单机平行分批排序问题的近似算法

考虑了工件有到达时间且拒绝工件总个数不超过某个给定值的单机平行分批排序问题.在该问题中,给定一个工件集和一台可以进行批处理加工的机器.每个工件有它的到达时间和加工时间;对于每个工件来说要么被拒绝要么被接受安排在机器的某一个批次里进行加工;一个工件如果被拒绝,则需支付该工件对应的拒绝费用.为了保证一定的服务水平,要求拒绝工件的总个数不超过给定值.目标是如何安排被接受工件的加工批次和加工次序使得其最大完工时间与被拒绝工件的总拒绝费用之和最小.该问题是NP-难的,对此给出了伪多项式时间动态规划精确算法,2-近似算法和完全多项式时间近似方案.     

Solution strategies for multi-stage wafer probing scheduling problem with reentry

The multi-stage wafer probing scheduling problem (M-WPSP) with reentry is a practical variation of the parallel-machine scheduling problem. Since the M-WPSP involves multiple product families, to be processed on multiple stages, with various job due dates, ready times, reentry, serial and batch operations, sequential-dependent setup time, it is more difficult to solve than the classical parallel-machine scheduling problems. In this paper, we consider two strategies to solve the M-WPSP with reentry, where the total machine workload must be minimized. These two strategies incorporate a global planning mechanism, in advance, to determine the required stage due date of job at each process stage to prevent the due date problems occurring at the final stage. The sequential strategy schedules the jobs at the required stages according to the sequence of manufacturing process. The parallel strategy is designed specifically for the reentrant characteristic. To evaluate the efficiency of the proposed strategies, a set of test problems involving four critical factors, the product family ratio, the temperature-change consideration, the tightness of due dates, and the ready time, are designed to test the quality of solutions under two levels of workload.     

An algorithm for a cutting stock problem on a strip

A cutting stock problem is formulated as follows: a set of rectangular pieces must be cut from a set of sheets, so as to minimize total waste. In our problem the pieces are requested in large quantities and the set of sheets are long rolls of material. For this class of problems we have developed a fast heuristic based on partial enumeration of all feasible patterns. We then tested the effectiveness on a set of test problems ranging from practical to random instances. Finally, the algorithm has been applied to check the asymptotic behaviour of the solution when a continuous stream of pieces is requested and cutting decisions are to be made while orders are still arriving.