考虑机器调整次数和产品质量的卷烟批量计划和柔性流水车间调度集成问题

针对卷烟企业生产中的批量计划和柔性流水车间调度集成问题,构建了整数规划模型,目标函数由卷烟生产时间、生产线调整次数、卷烟质量、库存成本四部分组成。鉴于该问题的NP-hard性,设计遗传算法进行求解,通过合理设计遗传算子,避免不可行解出现。应用某卷烟企业数据得到优化排产结果,与该企业之前依照经验排产方案进行对比,发现优化排程结果在减少品牌转换次数,提高生产的连续性方面具有明显优势。该算法已作为某卷烟企业排产人员的排产参考,应用于排产决策中,取得了良好的效果,对卷烟企业制定排产计划具有一定的实际指导意义。     

Solution approaches for the soft drink integrated production lot sizing and scheduling problem

In this paper we present a mixed integer programming model that integrates production lot sizing and scheduling decisions of beverage plants with sequence-dependent setup costs and times. The model considers that the industrial process produces soft drink bottles in different flavours and sizes, and it is carried out in two production stages: liquid preparation (stage I) and bottling (stage II). The model also takes into account that the production bottleneck may alternate between stages I and II, and a synchronisation of the production between these stages is required. A relaxation approach and several strategies of the relax-and-fix heuristic are proposed to solve the model. Computational tests with instances generated based on real data from a Brazilian soft drink plant are also presented. The results show that the solution approaches are capable of producing better solutions than those used by the company.     

Hybrid simulated annealing and MIP-based heuristics for stochastic lot-sizing and scheduling problem in capacitated multi-stage production system

This paper addresses lot sizing and scheduling problem of a flow shop system with capacity constraints, sequence-dependent setups, uncertain processing times and uncertain multi-product and multi-period demand. The evolution of the uncertain parameters is modeled by means of probability distributions and chance-constrained programming (CCP) theory. A new mixed-integer programming (MIP) model with big bucket time approach is proposed to formulate the problem. Due to the complexity of problem, two MIP-based heuristics with rolling horizon framework named non-permutation heuristic (NPH) and permutation heuristic (PH) have been performed to solve this model. Also, a hybrid meta-heuristic based on a combination of simulated annealing, firefly algorithm and proposed heuristic for scheduling is developed to solve the problem. Additionally, Taguchi method is conducted to calibrate the parameters of the meta-heuristic and select the optimal levels of the algorithm’s performance influential factors. Computational results on a set of randomly generated instances show the efficiency of the hybrid meta-heuristic against exact solution algorithm and heuristics.     

Multi-level,single-machine lot sizing and scheduling (with initial inventory)

This paper presents a mixed-integer program for the dynamic lot sizing and scheduling problem in a multi-level, single-machine environment. It turns out that in contrast to single-level problems the integration of initial inventory is a crucial aspect if generality should not be lost. It is shown how problem instances can efficiently be solved to suboptimality by using a so-called randomized regret based heuristic.     

Scheduling and lot sizing models for the single-vendor multi-buyer problem under consignment stock partnership

We consider a centralized supply chain composed of a single vendor serving multiple buyers and operating under consignment stock arrangement. Solving the general problem is hard as it requires finding optimal delivery schedule to the buyers and optimal production lot sizes. We first provide a nonlinear mixed integer programming formulation for the general scheduling and lot sizing problem. We show that the problem is NP-hard in general. We reformulate the problem under the assumption of ‘zero-switch rule’. We also provide a simple sequence independent lower bound to the solution of the general model. We then propose a heuristic procedure to generate a near-optimal delivery schedule. We assess the cost performance of that heuristic by conducting sensitivity analysis on the key model parameters. The results show that the proposed heuristic promises substantial supply-chain cost savings that increase as the number of buyers increases.     

The two-group heuristic to solve the multi-product,economic lot sizing and scheduling problem in flow shops

This paper presents a new and efficient heuristic to solve the multi-product, economic lot sizing and scheduling problem in flow shops. The problem addressed is that of making sequencing, lot sizing and scheduling decisions for a number of products so as to minimize the sum of setup costs, work-in-process inventory holding costs and final-products inventory holding costs while a given demand is fulfilled without backlogging. The proposed heuristic, called the two-group method (TG), assumes that the cycle time of each product is an integer multiple of a basic period and restricts these multiples to take either the value 1 or K where K is a positive integer. The products to be produced once each K basic period are then partitioned into K sub-groups and each sub-group is assigned to one and only one of the K basic periods of the global cycle. This method first determines a value for K and a feasible partition. Then, a production sequence is determined for each sub-group of products and a non-linear program is solved to determine lot sizes and a feasible schedule. We also show how to adapt our method to the case of batch streaming (transportation of sub-batches from one machine to the next). To evaluate its performance, the TG method was compared to both the common cycle method and a reinforced version of El-Najdawi’s job-splitting heuristic. Numerical results show that the TG method outperforms both of these methods.     

Economic lot sizes and vehicle scheduling

In this paper a relationship between the vehicle scheduling problem and the dynamic lot size problem is considered. For the latter problem we assume that order quantities for different products can be determined separately. Demand is known over our n-period production planning horizon. For a certain product our task is to decide for each period if it should be produced or not. If it is produced, what is its economic lot size? Our aim here is to minimize the combined set-up and inventory holding costs. The optimal solution of this problem is given by the well-known Wagner-Whitin dynamic lot size algorithm. Also many heuristics for solving this problem have been presented. In this article we point out the analogy of the dynamic lot size problem to a certain vehicle scheduling problem. For solving vehicle scheduling problems the heuristic algorithm developed by Clark and Wright in very often used. Applying this algorithm to the equivalent vehicle scheduling problem we obtain by analogy a simple heuristic algorithm for the dynamic lot size problem. Numerical results indicate that computation time is reduced by about 50% compared to the Wagner-Whitin algorithm. The average cost appears to be approximately 0.8% higher than optimum.     

Some insights into proportional lot sizing and scheduling

This paper deals with proportional lot sizing and scheduling (PLSP) and gives some insights into the properties of this problem. Such insights may be useful for developing heuristic and/or exact solution procedures. The emphasis of this paper is on the multi-level, multi-machine case. We provide a mixed-integer programming model, relate it to other models that can be found in the literature, and discuss characteristics which make solving instances of the PLSP-model a hard task.     

建筑废料现场分拣协调调度优化研究

工程项目施工现场废料分拣的效率对施工进度具有重要的影响。通过分析现场废料分拣实施过程,建立了带有限中间缓冲的混合流水车间调度模型。提出了收集阶段作业排序的动态自适应算法和后续设备分配问题的考虑缓冲区的设备分配规则,在此基础上设计了废料分拣模型的启发式算法,平衡各分区工作量,进一步搜索最优解,并推导了问题的一个低界。实验结果表明,所提出算法能很好地对施工现场废料分拣问题进行求解,具有良好的收敛性和较高的时间效率。     

Lot Streaming in a Two-stage Flow Shop with Set-up,Processing and Removal Times Separated

This paper considers the job (lot) scheduling problem for two-stage flow shops in which the movement of transfer batches (sublots) from the first stage to the next are allowed. Set-up, processing and removal times are considered as separable and independent of the order in which jobs are processed at any of two stages. An optimal transfer batch sizing and scheduling algorithm which has an objective of minimizing the maximum flow time (makespan) is developed and demonstrated by a numerical example.     

Joint rolling-horizon scheduling of materials processing and lot-sizing with sequence-dependent setups

A lot sizing and scheduling problem from a foundry is considered in which key materials are produced and then transformed into many products on a single machine. A mixed integer programming (MIP) model is developed, taking into account sequence-dependent setup costs and times, and then adapted for rolling horizon use. A relax-and-fix (RF) solution heuristic is proposed and computationally tested against a high-performance MIP solver. Three variants of local search are also developed to improve the RF method and tested. Finally the solutions are compared with those currently practiced at the foundry.     

A tabu search algorithm for solving economic lot scheduling problem

The economic lot scheduling problem has driven considerable amount of research. The problem is NP-hard and recent research is focused on finding heuristic solutions rather than searching for optimal solutions. This paper introduces a heuristic method using a tabu search algorithm to solve the economic lot scheduling problem. Diversification and intensification schemes are employed to improve the efficiency of the proposed Tabu search algorithm. Experimental design is conducted to determine the best operating parameters for the Tabu search. Results show that the tabu search algorithm proposed in this paper outperforms two well known benchmark algorithms.     

GRASP heuristic with path-relinking for the multi-plant capacitated lot sizing problem

This paper addresses the independent multi-plant, multi-period, and multi-item capacitated lot sizing problem where transfers between the plants are allowed. This is an NP-hard combinatorial optimization problem and few solution methods have been proposed to solve it. We develop a GRASP (Greedy Randomized Adaptive Search Procedure) heuristic as well as a path-relinking intensification procedure to find cost-effective solutions for this problem. In addition, the proposed heuristics is used to solve some instances of the capacitated lot sizing problem with parallel machines. The results of the computational tests show that the proposed heuristics outperform other heuristics previously described in the literature. The results are confirmed by statistical tests.     

Simultaneously scheduling multiple turns for steel color-coating production

This paper investigates a large-scale scheduling problem in the iron and steel industry, called color-coating production scheduling (CCPS). The problem is to generate multiple production turns for the galvanized coils that dynamically arrive from upstream lines within a given scheduling horizon, and at the same time determine the sequence of these turns so that the productivity and product quality are maximized while the production cost and the number of generated turns are minimized. We formulate this problem as a mixed integer nonlinear program and propose a tabu search heuristic to obtain satisfactory solutions. Results on real production instances show that the presented model and heuristic are more effective and efficient with comparison to manual scheduling. A practical scheduling system for CCPS combining the model and heuristic has been developed and successfully implemented in a major iron and steel enterprise in China.     

The hybrid flow shop scheduling problem

The scheduling of flow shops with multiple parallel machines per stage, usually referred to as the hybrid flow shop (HFS), is a complex combinatorial problem encountered in many real world applications. Given its importance and complexity, the HFS problem has been intensively studied. This paper presents a literature review on exact, heuristic and metaheuristic methods that have been proposed for its solution. The paper briefly discusses and reviews several variants of the HFS problem, each in turn considering different assumptions, constraints and objective functions. Research opportunities in HFS are also discussed.     

Routing and scheduling in project shipping

Tramp shipping companies are committed to transport a set of contracted cargoes and try to derive additional revenue from carrying optional spot cargoes. Here, we present a real life ship routing and scheduling problem for a shipping company operating in project shipping, a special segment of tramp shipping. This segment differs from more traditional tramp segments, as the cargoes are usually transported on a one-time basis. Because of the special nature of the cargoes, complicating requirements regarding stowage onboard the ships and cargo coupling must be considered while determining routes and schedules for the ships in the fleet. A mathematical model is presented and a tabu search heuristic is proposed to solve the problem. Computational results show that the tabu search heuristic provides optimal or near-optimal solutions in a reasonable amount of time, and that it can give significant improvements to manual planning for the shipping company.     

A search heuristic for the sequence-dependent economic lot scheduling problem

Almost all of the research on the economic lot scheduling problem (ELSP) has assumed that setup times are sequence-independent even though sequence-dependent problems are common in practice. Furthermore, most of the solution approaches that have been developed solve for a single optimal schedule when in practice it is more important to provide managers with a range of schedules of different length and complexity. In this paper, we develop a heuristic procedure to solve the ELSP problem with sequence-dependent setups. The heuristic provides a range of solutions from which a manager can choose, which should prove useful in an actual stochastic production environment. We show that our heuristic can outperform Dobson's heuristic when the utilization is high and the sequence-dependent setup times and costs are significant.     

Pricing,relaxing and fixing under lot sizing and scheduling

We present a novel mathematical model and a mathematical programming based approach to deliver superior quality solutions for the single machine capacitated lot sizing and scheduling problem with sequence-dependent setup times and costs. The formulation explores the idea of scheduling products based on the selection of known production sequences. The model is the basis of a matheuristic, which embeds pricing principles within construction and improvement MIP-based heuristics. A partial exploration of distinct neighborhood structures avoids local entrapment and is conducted on a rule-based neighbor selection principle. We compare the performance of this approach to other heuristics proposed in the literature. The computational study carried out on different sets of benchmark instances shows the ability of the matheuristic to cope with several model extensions while maintaining a very effective search. Although the techniques described were developed in the context of the problem studied, the method is applicable to other lot sizing problems or even to problems outside this domain.     

An Air Force Crew Allocation and Scheduling Problem

This paper considers an airline crew allocation and scheduling problem faced by certain divisions of the United States Air Force. Two variants of the problem under consideration were posed to us by the U.S. Air Force. This paper reports our experience with two heuristic methods developed, each applicable to either variant of the problem. Although the problem described herein is peculiar to this situation, the heuristic scheduling and dispatching rules developed have been found to be very effective and are generally applicable in other related contexts of routeing and crew and vehicle scheduling problems as well. The two algorithms developed have been applied to a coded set of real world data. The results indicate that each one of the two methods is preferable to the other for one of the two variants of the problem. This suggests an overall effective composite technique.     

Capacitated Lot Sizing for Injection Moulding: A Case Study

This paper considers the medium-term production smoothing problem for the injection moulding department of a Belgian firm. The problem is formulated as a series of one machine capacitated dynamic lot sizing problems, which are then solved by heuristic procedures. Computational results for real-life data are presented. It follows that the capacitated lot sizing approach succeeds in smoothing production such that subcontracting, which was often necessary with the E.O.Q. approach used by the firm, could be avoided in the future. Moreover, total set-up and inventory costs are reduced by about 20%.