The capacitated lot-sizing and scheduling problem with sequence-dependent setup costs and setup times

We consider the single machine capacitated lot-sizing and scheduling problem (CLSP) with sequence-dependent setup costs and non-zero setup times, with the additional feature that setups may be carried over from one period to the next, and that setups are preserved over idle periods. We provide an exact formulation of this problem as a mixed-integer program.It is well known that the CLSP is NP-hard. Therefore, we have also developed a heuristic for solving large problem instances. This is coupled with a procedure for obtaining a lower bound on the optimal solution. We carry out a computational study to test the accuracy of several different lower bounding linear relaxations and the approximate solution obtained by the heuristic. In our study, the average deviation of the heuristic solution from the corresponding exact solution depends on the size of the problem and ranges from 10 to 16%. The heuristic is more effective when there are many more products than there are planning periods. This is a desirable property from a practical viewpoint since most firms are likely to implement such a procedure on a rolling horizon basis, solving the problem repeatedly for a few periods at a time.     

需求随机的变质性产品生产计划模型

研究了能力约束的有限计划展望期生产计划问题,各周期的需求随机,库存产品存在变质且变质率为常数。建立了问题的期望值模型,目标函数为极小化生产准备成本、生产成本、库存成本的期望值。提出了随机模拟、遗传算法和启发式算法相结合的求解算法。用数值实例对模型和算法进行了验证,优化结果表明模型和算法是有效的。     

Two-Stage Stochastic Integer Programming Model for Multiperiod Sea Cargo Mix Problem in Container Shipping Industry

In this paper, we consider the cargo mix problem under uncertainty in the container shipping industry. We seek to determine the optimal cargo mix in a multiperiod planning horizon with the objective of maximizing the total expected profit derived from all freight bookings received in the planning horizon. We present a two-stage stochastic integer programming model and propose a heuristic algorithm for multiperiod sea cargo mix problem under uncertainty. Finally, numerical experiments on a wide range of randomly generated problem instances are conducted to demonstrate the efficiency of the algorithm.      

Heuristics for tactical time slot management: a periodic vehicle routing problem view

In this study, we consider a tactical problem where a time slot schedule for delivery service over a given planning horizon must be selected in each zone of a geographical area. A heuristic search evaluates each schedule selection by constructing a corresponding tactical routing plan of minimum cost based on demand and service time estimates. At the end, the schedule selection leading to the best tactical routing plan is selected. The latter can then be used as a blueprint when addressing the operational problem (i.e., when real customer orders are received and operational routes are constructed). We propose two heuristics to address the tactical problem. The first heuristic is a three‐phase approach: a periodic vehicle routing problem (PVRP) is first solved, followed by a repair phase and a final improvement phase where a vehicle routing problem (VRP) with time windows is solved for each period of the planning horizon. The second heuristic tackles the problem as a whole by directly solving a PVRP with time windows. Computational results compare the two heuristics under various settings, based on instances derived from benchmark instances for the VRP with time windows.     

A variable neighborhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine

This paper deals with the single machine scheduling problem to minimize the total weighted tardiness in the presence of sequence dependent setup. Firstly, a mathematical model is given to describe the problem formally. Since the problem is NP-hard, a general variable neighborhood search (GVNS) heuristic is proposed to solve it. Initial solution for the GVNS algorithm is obtained by using a constructive heuristic that is widely used in the literature for the problem. The proposed algorithm is tested on 120 benchmark instances. The results show that 37 out of 120 best known solutions in the literature are improved while 64 instances are solved equally. Next, the GVNS algorithm is applied to single machine scheduling problem with sequence dependent setup times to minimize the total tardiness problem without changing any implementation issues and the parameters of the GVNS algorithm. For this problem, 64 test instances are solved varying from small to large sizes. Among these 64 instances, 35 instances are solved to the optimality, 16 instances' best-known results are improved, and 6 instances are solved equally compared to the best-known results. Hence, it can be concluded that the GVNS algorithm is an effective, efficient and a robust algorithm for minimizing tardiness on a single machine in the presence of setup times.     

An incremental cost and resource smoothing heuristic for the capacitated lot sizing problem

A heuristic lot sizing algorithm is proposed for the multi-item, multi-period problem with limited resources. The objective is to minimize the total cost which consists of setup and inventory holding costs. The performance of the heuristic algorithm is compared with four existing heuristics.     

Design of robust cellular manufacturing system for dynamic part population considering multiple processing routes using genetic algorithm

In this paper, a comprehensive mathematical model is proposed for designing robust machine cells for dynamic part production. The proposed model incorporates machine cell configuration design problem bridged with the machines allocation problem, the dynamic production problem and the part routing problem. Multiple process plans for each part and alternatives process routes for each of those plans are considered. The design of robust cell configurations is based on the selected best part process route from user specified multiple process routes for each part type considering average product demand during the planning horizon. The dynamic part demand can be satisfied from internal production having limited capacity and/or through subcontracting part operation without affecting the machine cell configuration in successive period segments of the planning horizon. A genetic algorithm based heuristic is proposed to solve the model for minimization of the overall cost considering various manufacturing aspects such as production volume, multiple process route, machine capacity, material handling and subcontracting part operation.     

考虑机器检修的热轧钢管批量计划方法

本文从无缝钢管生产实际中提取并定义了周期性机器检修环境下的钢管热轧批量计划问题,基于无缝钢管生产的特殊性,将该问题抽象为一类考虑机器检修和机器调整时间的单机调度问题,并建立了以最小化机器闲置和机器调整时间为目标的数学模型.针对批量间的机器调整时间取决于钢管规格的变化这一特性,提出了最小调整时间排序规则,证明了该规则在不考虑检修计划时具有最优性.进而,以此为基础建立了循环求解框架,并设计了两阶段启发式算法.基于实际生产数据设计了多种问题规模的实验,验证了算法的有效性,并从实际应用角度对结果进行了分析.     

A multi-phase heuristic for the production routing problem

This study considers the production routing problem where a plant produces and distributes a single item to multiple retailers over a multi-period time horizon. The problem is to decide on when and how much to produce and stock at the plant, when and how much to serve and stock at each retailer, and vehicle routes for shipments such that the sum of fixed production setup cost, variable production cost, distribution cost, and inventory carrying cost at the plant and retailers is minimized. A multi-phase heuristic is proposed for the problem. The proposed heuristic is a mathematical programming-based heuristic that relies on formulating and solving restricted versions of the problem as mixed integer programs. The computational experiments on benchmark instances show favorable results with regard to the quality of the solutions found at the expense of higher computing times on large instances. In particular, the heuristic managed to find new best solutions for the 65% of benchmark instances.     

Scheduling and Lot Streaming in Flowshops with No-Wait in Process

Lot streaming involves splitting a production lot into a number of sublots, in order to allow the overlapping of successive operations, in multi-machine manufacturing systems. In no-wait flowshop scheduling, sublots are necessarily consistent, that is, they remain the same over all machines. The benefits of lot streaming include reductions in lead times and work-in-process, and increases in machine utilization rates. We study the problem of minimizing the makespan in no-wait flowshops producing multiple products with attached setup times, using lot streaming. Our study of the single product problem resolves an open question from the lot streaming literature. The intractable multiple product problem requires finding the optimal number of sublots, sublot sizes, and a product sequence for each machine. We develop a dynamic programming algorithm to generate all the nondominated schedule profiles for each product that are required to formulate the flowshop problem as a generalized traveling salesman problem. This problem is equivalent to a classical traveling salesman problem with a pseudopolynomial number of cities. We develop and computationally test an efficient heuristic for this problem. Our results indicate that solutions can quickly be found for flowshops with up to 10 machines and 50 products. Moreover, the solutions found by our heuristic provide a substantial improvement over previously published results.     

The period traveling salesman problem: a new heuristic algorithm

A new, simple and effective heuristic algorithm has been developed for the period traveling salesman problem. Computational results obtained from the test problems taken from the literature indicate that the algorithm compares well in terms of accuracy with other existing algorithms, finding a larger number of best solutions. Moreover, its average percentage error and its worst ratio of solution to the best-known solution are smaller than those of the other existing algorithms.Scope and purposeIn the period traveling salesman problem, a traveling salesman must visit each city a fixed number of times over a given m-day planning period. Each city specifies a set of sequences of visit days and the visit days are assigned to the city by selecting one of these sequences. Moreover, for each day of the planning period, a not empty tour must be generated by connecting the salesman home city and the cities that must be visited on that day. The salesman objective is to minimize the total distance traveled over the entire m-day period. For this problem, arising in various situations such as mail delivery or lawn-care services, the paper proposes a simple and effective heuristic algorithm where an improvement procedure is embedded within a tour construction type procedure.     

Using tabu search with ranking candidate list to solve production planning problems with setups

This study considers production planning problems involving multiple products, multiple resources, multiple periods, setup times, and setup costs. It can be formulated as a mixed integer program (MIP). Solving a realistic MIP production planning problem is NP-hard; therefore, we use tabu search methods to solve such a difficult problem. Furthermore, we improve tabu search by a new candidate list strategy, which sorts the neighbor solutions using post-optimization information provided by the final tableau of the linear programming simplex algorithm. A neighbor solution with higher priority in the ranking sequence has a higher probability of being the best neighbor solution of a current solution. According to our experiments, the proposed candidate list strategy tabu search produces a good solution faster than the traditional simple tabu search. This study also suggests that if the evaluation of the entire neighborhood space in a tabu search algorithm takes too much computation and if an efficient and effective heuristic to rank the neighbor solutions can be developed, the speed of tabu search algorithm could be significantly increased by using the proposed candidate list strategy.     

A two-stage flow shop scheduling problem on a batching machine and a discrete machine with blocking and shared setup times

Motivated by applications in iron and steel industry, we consider a two-stage flow shop scheduling problem where the first machine is a batching machine subject to the blocking constraint and the second machine is a discrete machine with shared setup times. We show that the problem is strongly NP-hard when the objective is to minimize the makespan. When solved with a heuristic priority rule, the worst case ratio with the minimum makespan is 2. For a more general objective, the minimization of a linear combination of the makespan and the total blocking time, a quadratic mixed integer program is presented first. Then we pinpoint two cases with polynomial time algorithms: the case without blocking constraint and the case with a given job sequence. Also for the general objective, we analyze an approximation algorithm. Finally, we evaluate the algorithms, giving experimental results on randomly generated test problems.     

Rationing mechanisms and inventory control-policy parameters for a divergent supply chain operating with lost sales and costs of review

We consider a static divergent two-stage supply chain with one distributor and many retailers. The unsatisfied demands at the retailers’ end are treated as lost sales, whereas the unsatisfied demand is assumed to be backlogged at the distributor. The distributor uses an inventory rationing mechanism to distribute the available on-hand inventory among the retailers, when the sum of demands from the retailers is greater than the on-hand inventory at the distributor. The present study aims at determining the best installation inventory control-policy or order-policy parameters such as the base-stock levels and review periods, and inventory rationing quantities, with the objective of minimizing the total supply chain costs (TSCC) consisting of holding costs, shortage costs and review costs in the supply chain over a finite planning horizon. An exact solution procedure involving a mathematical programming model is developed to determine the optimum TSCC, base-stock levels, review periods and inventory rationing quantities (in the class of periodic review, order-up-to S policy) for the supply chain model under study. On account of the computational complexity involved in optimally solving problems over a large finite time horizon, a genetic algorithm (GA) based heuristic methodology is presented.     

Assigning multiple activities to work shifts

In some companies such as large retail stores, the employees perform different activities (e.g., cashier or clerk in a specific department) to respond to a customer demand for each activity that varies over the planning horizon and must be fulfilled as soon as possible. For a given time period, this demand translates into an ideal number of employees required for the corresponding activity. During a work shift, an employee can be assigned to several activities that are interruptible at any time and subject to operational constraints (required skills, minimum and maximum assignment durations). Given work shifts already assigned to the employees, the multi-activity assignment problem (MAAP) consists of assigning activities to the shifts such that the activity demands are satisfied as best as possible over the planning horizon. In this paper, we propose three integer programming models for the MAAP and develop various heuristics based on mathematical programming techniques. Computational results obtained on randomly generated MAAP instances show that a heuristic column generation method embedded into a rolling horizon procedure provides the best results in general.     

A tabu search heuristic for a sequence-dependent and time-dependent scheduling problem on a single machine

This paper introduces a tabu search heuristic for a production scheduling problem with sequence-dependent and time-dependent setup times on a single machine. The problem consists in scheduling a set of dependent jobs, where the transition between two jobs comprises an unrestricted setup that can be performed at any time, and a restricted setup that must be performed outside of a given time interval which repeats daily in the same position. The setup time between two jobs is thus a function of the completion time of the first job. The tabu search heuristic relies on shift and swap moves, and a surrogate objective function is used to speed-up the neighborhood evaluation. Computational experiments show that the proposed heuristic consistently finds better solutions in less computation time than a recent branch-and-cut algorithm. Furthermore, on instances where the branch-and-cut algorithm cannot find the optimal solution, the heuristic always identifies a better solution.     

Optimal sampling-rates and tracking properties of digital LQ and LQG tracking controllers for systems with an exogenous component and costs associated to sampling

In this paper it is shown that if costs are associated to sampling operations which are added to a performance criterion, the minimization of this new performance criterion results in a controller operated at an optimal sampling rate. This, under the assumptions that the system is periodically sampled, the applied control is kept fixed between every two sampling instances and some technical conditions are met. In case the considered planning horizon in the performance criterion is finite an algorithm is devised which calculates in a finite number of steps the optimal sampling period. It is shown that the technical conditions mentioned above are satisfied by the finite planning horizon time-varying LQG tracking problem. Since stability is a major requirement in controller design we also consider the case of an infinite planning horizon. This analysis is focused on the time-invariant digital LQ tracking problem. Given some mild regularity conditions a numerical algorithm is presented that approximates the optimal solution within any prespecified error norm. It is shown that also in this case an optimal sampling-rate exists. The algorithm for determining the optimal sampling period if the planning horizon is finite is illustrated in an economic example.     

A heuristic solution procedure for the dynamic lot sizing problem with remanufacturing and product recovery

Here we discuss the lot sizing problem of product returns and remanufacturing. Let us consider a forecast of demands and product returns over a finite planning horizon — the problem is to determine an optimal production plan. This consists of either manufacturing new products or remanufacturing returned units, and in this way meets both demands at minimum costs. The costs of course are the fixed set-up expenses associated with manufacturing and/or remanufacturing lots and also the inventory holding costs of stocks kept on hand.In addition to showing that a general instance of this problem is NP-Hard, we develop an alternative mixed-integer model formulation for this problem and contrast it to the formulation commonly used in the literature. We show that when integrality constraints are relaxed, our formulation obtains better bounds. Our formulation incorporates the fact that every optimal solution can be decomposed into a series of well-structured blocks with distinct patterns in the way in which set-ups for manufacturing and remanufacturing occur. We then construct a dynamic programming based heuristic that exploits the block structure of the optimal solution. We also propose some improvement schemes as well. Finally, our numerical testing shows that the heuristic performs very well as intended.     

A two phase variable neighborhood search for the multi-product inventory routing problem

We address a multi-product inventory routing problem and propose a two-phase Variable Neighborhood Search (VNS) metaheuristic to solve it. In the first phase, VNS is used to solve a capacitated vehicle routing problem at each period to find an initial solution without taking into account the inventory. In the second phase, we iteratively improve the initial solution while minimizing both the transportation and inventory costs. For this, we propose two different algorithms, a Variable Neighborhood Descent and a Variable Neighborhood Search. We present an heuristic and a Linear Programming formulation, which are applied after each local search move, to determine the amount of products to collect from each supplier at each period. During the exploration, we use priority rules for suppliers and vehicles, based on the current delivery schedule over the planning horizon. Computational results show the efficiency of the proposed two-phase approach.     

Capacitated facility location problem with general setup cost

This paper presents an extension of the capacitated facility location problem (CFLP), in which the general setup cost functions and multiple facilities in one site are considered. The setup costs consist of a fixed term (site setup cost) plus a second term (facility setup costs). The facility setup cost functions are generally non-linear functions of the size of the facility in the same site. Two equivalent mixed integer linear programming (MIP) models are formulated for the problem and solved by general MIP solver. A Lagrangian heuristic algorithm (LHA) is also developed to find approximate solutions for this NP-hard problem. Extensive computational experiments are taken on randomly generated data and also well-known existing data (with some necessary modifications). The detailed results are provided and the heuristic algorithm is shown to be efficient.