A genetic algorithm/mathematical programming approach to solve a two-level soft drink production problem

This study applies a genetic algorithm embedded with mathematical programming techniques to solve a synchronized and integrated two-level lot sizing and scheduling problem motivated by a real-world problem that arises in soft drink production. The problem considers a production process compounded by raw material preparation/storage and soft drink bottling. The lot sizing and scheduling decisions should be made simultaneously for raw material preparation/storage in tanks and soft drink bottling in several production lines minimizing inventory, shortage and setup costs. The literature provides mixed-integer programming models for this problem, as well as solution methods based on evolutionary algorithms and relax-and-fix approaches. The method applied by this paper uses a new approach which combines a genetic algorithm (GA) with mathematical programming techniques. The GA deals with sequencing decisions for production lots, so that an exact method can solve a simplified linear programming model, responsible for lot sizing decisions. The computational results show that this evolutionary/mathematical programming approach outperforms the literature methods in terms of production costs and run times when applied to a set of real-world problem instances provided by a soft drink company.     

可重入混合流水车间调度的拉格朗日松弛算法

为了有效提升多重入车间的生产效率,考虑了实际生产中检查和修复过程对于逐层制造的可重入生产系统的重要性,提出了基于拉格朗日松弛算法的可重入混合流水车间的调度方法.首先进行了问题域的描述,并在此基础上以最小化加权完成时间为调度目标,建立数学规划模型.针对该调度问题提出了基于松弛机器能力约束的拉格朗日松弛算法,使松弛问题分解成工件级子问题,并使用动态规划方法建立递归公式,求解工件级子问题.随后,使用次梯度算法求解拉格朗日对偶问题.最后,对各种不同问题规模进行了仿真实验,结果表明,所提出的调度算法能够在合理的时间内获得满意的近优解.     

基于Petri网的改进检验过程调度算法

原材料的检验方法在生产计划中起着关键的作用.根据检验过程的特点,提出一种改进的检验过程调度算法.该算法解决了此前多处理器调度算法用于分支检验时仅根据原材料投产时间对材料进行调度所产生的问题.改进的算法增加了原材料检验任务的紧迫度的概念,针对检验时间较长的材料,投产时间紧迫的任务实现了有效调度,进而提高生产效率.同时算法结合高级颜色时间Petri网,模拟一个实际企业管理系统,对改进的检验任务调度算法建模并进行仿真测试.测试结果表明,改进的算法在生产计划的检验过程中,检验成功率和检验员的工作效率较先前算法都有较大提高.     

解并行机模糊调度问题的自适应遗传算法

针对家纺企业车间调度的实际情况,建立了一种产品优先级约束的模糊车间调度模型。在模型中,完工时间和交货期都是模糊的,交货期平均满意度最大为调度目标。基于此模型,提出了一种自适应的遗传算法,该算法通过比例选择及局部搜索保证种群的优良特性,并通过自动调节变异率和交叉率的方式保证种群的多样性,有效跳出局部收敛。仿真结果表明,自适应遗传算法能有效求解,并优于免疫遗传算法。     

Dynamically scheduling ships to multiple continuous berth spaces in an iron and steel complex

This paper studies the problem of dynamically scheduling ships to multiple continuous berth spaces at the raw material docks in an iron and steel complex with the objective of minimizing the total weighted service time. We propose two mathematical models and develop an improved Lagrangian relaxation algorithm to solve the problem. Based on the problem structure, six properties are observed that help speed up the procedures of solving the sub-problems, updating Lagrangian multipliers and obtaining feasible solutions, respectively. Computational results on 50 real data problems and 120 randomly generated problems show that the algorithm generates good solutions in short time and that using the properties can reduce by more than 80% the computation time of the algorithm.     

An integrated production inventory model under interactive fuzzy credit period for deteriorating item with several markets

The presence of multiple markets create profitable opportunities to the supply chain system. In this regard, this paper consists of the joint relationship between a manufacturer and multiple markets in which manufacturer offers part-payment to the markets due to their collection of finished products during the production run time. Here it is also considered that manufacturer is facilitated with credit period by raw material supplier where credit period has been presented as an interactive fuzzy fashion. In this paper, two types of deterioration have been assumed such as one for finished products and the other for raw materials. A solution algorithm is presented to get fuzzy optimal profit for the proposed integrated production inventory system optimizing production run time. A numerical example is used to illustrate the proposed model. Finally, sensitivity analysis has been carried out with respect to the major parameters to demonstrate the feasibility of the proposed model.     

面向MES的钢铁烧结生产原料供应调度系统

针对某钢铁企业烧结厂烧结生产原料供应调度问题,提出了面向MES的烧结生产原料供应调度系统的整体功能、结构和设计原则,并采用了模型加启发式算法和人际交互相结合的烧结生产原料供应调度计划编制方法。设计并开发了烧结生产原料供应调度系统,通过现场数据离线仿真表明:该系统可快速准确地编制出符合现场情况、满足工艺要求、高效的烧结生产原料供应调度计划。     

An optimal batch size for a JIT manufacturing system

This paper addresses the problem of a manufacturing system that procures raw materials from suppliers in a lot and processes them to convert to finished products. It proposes an ordering policy for raw materials to meet the requirements of a production facility. In turn, this facility must deliver finished products demanded by outside buyers at fixed interval points in time. In this paper, first we estimate production batch sizes for a JIT delivery system and then we incorporate a JIT raw material supply system. A simple algorithm is developed to compute the batch sizes for both manufacturing and raw material purchasing policies. Computational experiences of the problem are also briefly discussed.     

单台批处理机生产运输协调合作博弈调度问题

研究单台批处理机生产与生产前运输的协调调度问题,目标函数为最小化与完成时间相关的生产总成本.以工件为博弈方,以联盟的最大成本节省为特征函数,将调度问题转换为合作博弈模型.针对相同运输时间与加工时间的情形,证明该合作博弈具有非空核,beta规则可得一个核分配.针对一般问题,设计Q-learning算法求解联盟最优调度,并利用beta规则对节省的成本进行分配.数值算例验证了合作博弈模型的可行性以及Q-learning算法与beta规则对节省成本分配的有效性.     

基于预测与分解策略的大规模炼油过程生产调度算法

炼油生产调度为混合整数规划问题,随着规模的增大,其求解时间随问题规模呈指数增加,使得大规模长周期炼油生产调度问题难以在合理的时间内求解.针对该问题,本文提出了一种基于生产任务预测与分解策略的炼油生产调度算法,该算法能在短时间内获得大规模调度问题的满意解.所提算法将原问题沿时间轴分解为若干个调度时长相同的单时间段子问题,并设计了基于深度学习的单时间段生产任务(组分油产量)预测模型,用于协调子问题的求解.其中,生产任务预测模型通过易于获得的小规模问题的全局最优调度方案训练得到.最后,通过与商业求解器Cplex以及现有算法的对比,实验结果表明了所提算法的有效性.     

求解混流装配线调度问题的蚁群算法

以最小化总的传送中断时间为目标函数的混流装配线调度问题是丰田生产方式中自动化概念的一个重要问题,而新颖的蚁群算法具有通用性、鲁棒性、并行搜索以及易于与其他启发式算法结合的优点,可以解决多种组合优化问题,对其进行了改进,以便更适于求解混流装配线的调度问题。实验表明：改进的蚁群算法解决了混流装配线的调度问题,得到了优于分支定界法、模拟退火法和遗传算法的可行解。     

面向移动云计算任务调度的改进鸟群算法研究

针对移动云计算环境下的任务调度存在耗时长、设备能耗高的问题,提出了一种基于改进的鸟群算法(improved bird swarm algorithm,IBSA)的任务调度策略。首先,构建了以能耗和时间为主的移动云任务调度模型;其次,提出了自适应感知系数和社会系数,避免了算法陷入局部最优;构建了学习因子优化飞行行为,保证了个体寻优能力;最后,任务调度目标函数作为鸟群个体的适应度函数参与算法的迭代更新。仿真结果表明相比于蚁群算法、粒子群算法、鲸鱼算法等,改进的鸟群算法在移动云计算任务调度方面具有良好的效果,能够有效地节省时间和降低能耗。     

A multi-objective customer orders assignment and resource leveling in make-to-order manufacturing

This paper presents integer programming formulations and compares two approaches – weighting and lexicographic – to the multi‐objective, long‐term production scheduling in make‐to‐order manufacturing, where both maximization of customer service level and best utilization of production resources are integrated in the objective function. The problem objective is to assign customer orders for various product types and with various due dates to planning periods and to select machines for assignment in every period to complete all the orders with minimum numbers of tardy and early orders and with a leveled machine assignment over a planning horizon. The two approaches are applied to optimize long‐term production schedules in a flexible flowshop with parallel machines. Numerical examples modeled after a real‐world flexible assembly line in the electronics industry are provided and some computational results are reported.     

基于深度强化学习的模糊作业车间调度问题

针对具有模糊加工时间和模糊交货期的作业车间调度问题,以最小化最大完工时间为目标,以近端策略优化(PPO)算法为基本优化框架,提出一种LSTM-PPO(proximal policy optimization with Long short-term memory)算法进行求解.首先,设计一种新的状态特征对调度问题进行建模,并且依据建模后的状态特征直接对工件工序进行选取,更加贴近实际环境下的调度决策过程;其次,将长短期记忆(LSTM)网络应用于PPO算法的行动者-评论者框架中,以解决传统模型在问题规模发生变化时难以扩展的问题,使智能体能够在工件、工序、机器数目发生变化时,仍然能够获得最终的调度解.在所选取的模糊作业车间调度的问题集上,通过实验验证了该算法能够取得更好的性能.     

Integrated order acceptance and supply chain scheduling problem with supplier selection and due date assignment

The importance, benefits, and impact of integration of decisions within supply chains have long been investigated by many researchers. Order acceptance and supplier selection are two of the most critical decisions for supply chain managers. Throughout the process of order acceptance, a manufacturer has to decide which orders to be accepted and processed and based on the accepted orders, the volume of required raw material is determined. On the other hand, a manufacturer aims to choose one or several suppliers among all possible choices to provide sufficient raw material for the accepted orders, subject to different criteria such as list price, transportation cost, etc. This paper addresses an integrated framework for profit maximization in an integrated supplier selection, order acceptance and scheduling problem in a single-machine environment with multiple customers. There is substantial literature on the problems of supplier selection and order acceptance; however, to the best of our knowledge, this paper is the first research that integrates these essential decisions in the form of a mathematical model to maximize the total profit. The problem is NP-hard in nature; therefore, solving to optimality is not practically possible for problems with medium and large size. For that purpose, we developed a Heuristic Algorithm (HA) to solve the problem above in a reasonable time, with proper accuracy. Results from this heuristic algorithm are compared with that of a commercial solver (GAMS) and the well-known Genetic Algorithm (GA) and Variable Neighborhood Search (VNS). Computational experiments demonstrate that the developed heuristic algorithm is more efficient in comparison with other tested methods.     

求解job shop调度问题的量子粒子群优化算法*

针对粒子群优化算法搜索空间有限、容易出现早熟现象的缺陷,提出将量子粒子群优化算法用于求解作业车间调度问题。求解时,将每个调度按照一定的规则编码为一个矩阵,并以此矩阵作为算法中的粒子;然后根据调度目标确定目标函数,并按照量子粒子群优化算法的进化规则在调度空间内搜索最优解。仿真实例结果证明,该算法具有良好的全局收敛性能和快捷的收敛速度,调度效果优于遗传算法和粒子群优化算法。     

一种远程医疗系统中多专家会诊的调度问题求解*

为解决病人在医疗会诊中多重复杂的问题,提出了用群体决策的方法调度多专家为病人进行远程医疗会诊。该算法分析了多专家会诊调度的特点,把调度问题转换为图论问题,建立了数学模型,采用贪心算法求得目标函数值,进行迭代扫描,逐步求出最优的多专家会诊调度结果。实验结果表明,该算法很好地解决了用较少等待时间来实现较多集体会诊的问题,也很好地解决了每次集体会诊的专家成员数最优问题,为多专家调度会诊问题提供了一个可行性的解。     

Production scheduling and vehicle routing with time windows for perishable food products

We propose a nonlinear mathematical model to consider production scheduling and vehicle routing with time windows for perishable food products in the same framework. The demands at retailers are assumed stochastic and perishable goods will deteriorate once they were produced. Thus the revenue of the supplier is uncertain and depends on the value and the transaction quantity of perishable products when they are carried to retailers. The objective of this model is to maximize the expected total profit of the supplier. The optimal production quantities, the time to start producing and the vehicle routes can be determined in the model simultaneously. Furthermore, we elaborate a solution algorithm composed of the constrained Nelder–Mead method and a heuristic for the vehicle routing with time windows to solve the complex problem. Computational results indicate our algorithm is effective and efficient.     

Integrating simulation and optimization to schedule loading operations in container terminals

In this paper, a simulation optimization method for scheduling loading operations in container terminals is developed. The method integrates the intelligent decision mechanism of optimization algorithm and evaluation function of simulation model, its procedures are: initializing container sequence according to certain dispatching rule, then improving the sequence through genetic algorithm, using simulation model to evaluate objective function of a given scheduling scheme. Meanwhile, a surrogate model based on neural network is designed to predict objective function and filter out potentially bad solutions, thus to decrease the times of running simulation model. Numerical tests show that simulation optimization method can solve the scheduling problem of container terminals efficiently. And the surrogate model can improve the computation efficiency of simulation optimization.     

协同设计任务调度的多步Q学习算法

首先建立任务调度问题的目标模型,在分析Q学习算法的基础上,给出调度问题的马尔可夫决策过程描述;针对任务调度的Q学习算法更新速度慢的问题,提出一种基于多步信息更新值函数的多步Q学习调度算法.应用实例表明,该算法能够提高收敛速度,有效地解决任务调度问题.