A comparative study of heuristic algorithms on Economic Lot Scheduling Problem

The Economic Lot Scheduling Problem (ELSP) has been well-researched for more than 40 years. As the ELSP has been generally seen as NP-hard, researchers have focused on the development of efficient heuristic approaches. In this paper, we consider the time-varying lot size approach to solve the ELSP. A computational study of the existing solution algorithms, Dobson’s heuristic, Hybrid Genetic algorithm, Neighborhood Search heuristics, Tabu Search and the newly proposed Simulated Annealing algorithm are presented. The reviewed methods are first tested on two well-known problems, those of Bomberger’s [Bomberger, E. E. (1966). A dynamic programming approach to a lot size scheduling problem. Management Science 12, 778–784] and Mallya’s [Mallya, R (1992). Multi-product scheduling on a single machine: A case study. OMEGA: International Journal of Management Science 20, 529–534] problems. We show the Simulated Annealing algorithm finds the best known solution to these problems. A similar comparison study is performed on various problem sets previously suggested in the literature. The results show that the Simulated Annealing algorithm outperforms Dobson’s heuristic, Hybrid Genetic algorithm and Neighborhood search heuristics on these problem sets. The Simulated Annealing algorithm also shows faster convergence than the best known Tabu Search algorithm, yet results in solutions of a similar quality. Finally, we report the results of the design of experiment study which compares the robustness of the mentioned meta-heuristic techniques.     

A resource-constrained assembly job shop scheduling problem with Lot Streaming technique

To ensure effective shop floor production, it is vital to consider the capital investment. Among most of the operational costs, resource must be one of the critical cost components. Since each operation consumes resources, the determination of resource level is surely a strategic decision. For the first time, the application of Lot Streaming (LS) technique is extended to a Resource-Constrained Assembly Job Shop Scheduling Problem (RC_AJSSP). In general, AJSSP first starts with Job Shop Scheduling Problem (JSSP) and then appends an assembly stage for final product assembly. The primary objective of the model is the minimization of total lateness cost of all final products. To enhance the model usefulness, two more experimental factors are introduced as common part ratio and workload index. Hence, an innovative approach with Genetic Algorithm (GA) is proposed. To examine its goodness, Particle Swarm Optimization (PSO) is the benchmarked method. Computational results suggest that GA can outperform PSO in terms of optimization power and computational effort for all test problems.     

Optimizing a closed-loop supply chain with manufacturing defects and quality dependent return rate

The paper considers a closed-loop serial supply chain consisting of a raw material supplier, a manufacturer, a retailer and a collector who collects the used product from consumers. The retailer's demand is met up by both manufacturing and remanufacturing. The manufacturing process is assumed to be imperfect as it can produce some defectives which are reworked in the same cycle itself. The remanufacturing of used items solely depends on the quality level of collected items. Two mathematical models are developed. The first model considers a single manufacturing–remanufacturing cycle, while the second model considers multiple manufacturing and remanufacturing cycles. Both the models are solved using algorithms developed for sequential and global optimizations. Numerical studies show that (i) the acceptance quality level of returned items and the length of the replenishment cycle for the retailer are lower in case of sequential optimization than those in global optimization, (ii) integration among supply chain members results in less number of shipments from the manufacturer to the retailer, and (iii) the joint total profit is higher when the integrated approach is adopted. The percentage increase in joint total profit with the integrated policy is 1.24% in the first model while it is 0.544% in the second model.     

An adaptive pull strategy for remanufacturing systems

Recently, remanufacturing systems have been studied from various viewpoints. Van der Laan and Teunter (Eur J Oper Res 175(2):1084–1102, 2006), for example, proposed simple heuristics for push and pull remanufacturing strategies. However, because they are only simple heuristics they are not very useful in a stochastic demand situation. An adaptive strategy should be incorporated into the pull strategy to improve performance; therefore, we propose an adaptive pull strategy for remanufacturing systems that can control manufacturing and remanufacturing rates in the remanufacturing system. The performance and effectiveness of our proposed system is analyzed by Markov analysis, and the results are shown in this paper.     

基于混合遗传算法的车间生产调度问题研究

解决车间生产调度问题的目的不仅仅是为了缩短生产周期,更重要的是为了提高生产效率,降低生产成本。现大部分国有制造企业在车间生产过程中采用的是人工调度,调度时主要依赖于调度经验,调度效率不高且易出错。将遗传算法和模拟退火算法相结合,提出了解决车间调度问题的混合遗传算法,并给出了一种编码方法以及建立了相应的解码规则。遗传算法的引入保证了解的全局最优性,仿真后表明了该混合算法的可行性和有效性,且能够有效地提高搜索效率,改进了收敛性能。     

Production planning optimization for manufacturing and remanufacturing system in stochastic environment

This article studies a single item dynamic lot sizing problem with manufacturing and remanufacturing provisions. The demands and returns are considered as both stochastic and deterministic. There are two inventories recoverable and serviceable inventory. We developed a dynamic programming based model with objective to determine the quantities that have to be manufactured or re-manufactured at each period in order to minimize the total cost, including production cost, holding cost for returns and finished goods, and backlog cost. Also, unit production cost is also taken as variable in case of deterministic case. Finally, a numerical example for each of deterministic and stochastic model is worked out to illustrate how the model is applied and to prove its feasibility.     

用蚁群算法求解Job-Shop问题的机器分解方法

针对生产调度中Job-Shop问题,蚁群算法在求解Job-Shop问题时有计算量大的缺点,为了提高求解效率,将机器分解方法引入蚁群算法.机器分解方法在每次迭代中蚂蚁仅在子图中构造部分解,并与上次迭代中其他机器上的顺序共同构成本次解,提高了蚁群算法求解Job-Shop问题的效率.并且在算法中提出了一种新的状态转移规则和设计了蚂蚁起点位置的方法.通过在Benchmark算例上的仿真,与原有的一类集中式求解的蚁群算法作了比较,结果显示改进后的算法取得了较好的结果,大大缩短了计算时间,说明机器分解方法的有效性.     

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.     

A fuzzy hierarchical reinforcement learning based scheduling method for semiconductor wafer manufacturing systems

Scheduling semiconductor wafer manufacturing systems has been viewed as one of the most challenging optimization problems owing to the complicated constraints, and dynamic system environment. This paper proposes a fuzzy hierarchical reinforcement learning (FHRL) approach to schedule a SWFS, which controls the cycle time (CT) of each wafer lot to improve on-time delivery by adjusting the priority of each wafer lot. To cope with the layer correlation and wafer correlation of CT due to the re-entrant process constraint, a hierarchical model is presented with a recurrent reinforcement learning (RL) unit in each layer to control the corresponding sub-CT of each integrated circuit layer. In each RL unit, a fuzzy reward calculator is designed to reduce the impact of uncertainty of expected finishing time caused by the rematching of a lot to a delivery batch. The results demonstrate that the mean deviation (MD) between the actual and expected completion time of wafer lots under the scheduling of the FHRL approach is only about 30 % of the compared methods in the whole SWFS.     

Assessing the benefits of remanufacturing option under one-way substitution and capacity constraint

In this article, we investigate the profitability of remanufacturing option when the manufactured and remanufactured products are segmented to different markets and the production capacity is finite. A single period profit model under substitution is constructed to investigate the system conditions under which remanufacturing is profitable. We present analytical findings and computational results to show profitability of remanufacturing option under substitution policy subject to a capacity constraint of the joint manufacturing/remanufacturing facility.     

Supply chain-oriented two-stage assembly flowshops with sequence-dependent setup times

Supply chain-oriented scheduling problems have received recent recognition among production research scholars due to their ability in integrating production planning and control across manufacturing systems. This study contributes to the literature of the distributed scheduling problems developing an original Mixed-Integer Linear Programming (MILP) formulation to the Distributed Two-Stage Assembly Flowshop Scheduling Problem with Sequence-Dependent Setup Times (DTSAFSP-SDSTs). Besides, the Iterated Greedy algorithm is extended to effectively solve this relatively complex production scheduling situation considering the makespan as the optimization criterion. Extensive numerical tests and statistical analyses are conducted to evaluate the effectiveness of the developed solution algorithm. Results showed that the Improved Iterated Greedy (IIG) algorithm yields the best solution in nearly all of the large-scale instances. The statistical test of significance confirmed that IIG is superior to the current-best-performing algorithm. This study contributes to the transition from standalone optimization to integrated production planning and control of distributed manufacturing systems.     

基于元学习推荐的优化算法自动选择框架与实证分析

算法选择的目的是从众多可用优化算法中自动地选出最适用于当前问题的算法。针对算法选择问题提出了基于元学习推荐的优化算法自动选择框架。依据此框架,以多模式资源受限的项目调度问题为实证数据集,设计实现了遗传算法（GA）、粒子群算法（PSO）和模拟退火算法（SA）三种算法的自动选择过程。从项目调度问题数据库中随机选取了378个问题算例,提取其中的固有特征和统计特征作为元数据,并利用前馈型神经网络（FNN）算法训练获得用于预测的元模型对未见算例作出预测。实证结果表明两选一的算法预测准确率最高可超过95%,交叉验证准确率平均达到85%;三选一的算法预测准确率最高可达92%,交叉验证准确率平均超过80%。实证结果验证了所提算法选择框架是成功的,基于元学习思想的优化算法自动选择方法是可行的。     

应用遗传模拟退火算法实现资源受限项目调度

针对以最小化项目工期为目标的资源受限项目调度问题（RCPSP）,提出将模拟退火算法融合到遗传算法中,以改善遗传算法局部搜索性能,增强进化能力的遗传模拟退火算法——RCPSPGSA。在每次进化迭代过程中,下一代种群的个体需经过模拟退火算法改进,并通过在每次迭代结束前进行降温操作保证遗传算法和模拟退火算法具有相同的收敛方向和速度。算法在RCPSP标准测试问题库PSPLIB上进行数值仿真实验,并采用正交实验分析法解决参数选择问题。实验结果证明选择的参数组合具有突出的性能,RCPSPGSA是求解RCPSP的有效算法。     

An Adaptive Bumble Bees Mating Optimization algorithm

The finding of the suitable parameters of an evolutionary algorithm, as the Bumble Bees Mating Optimization (BBMO) algorithm, is one of the most challenging tasks that a researcher has to deal with. One of the most common used ways to solve the problem is the trial and error procedure. In the recent few years, a number of adaptive versions of every evolutionary and nature inspired algorithm have been presented in order to avoid the use of a predefined set of parameters for all instances of the studied problem. In this paper, an adaptive version of the BBMO algorithm is proposed, where initially random values are given to each one of the parameters and, then, these parameters are adapted during the optimization process. The proposed Adaptive BBMO algorithm is used for the solution of the Multicast Routing Problem (MRP). As we would like to prove that the proposed algorithm is suitable for solving different kinds of combinatorial optimization problems we test the algorithm, also, in the Probabilistic Traveling Salesman Problem (PTSP) and in the Hierarchical Permutation Flowshop Scheduling Problem (HPFSP). Finally, the algorithm is tested in four classic benchmark functions for global optimization problems (Rosenbrock, Sphere, Rastrigin and Griewank) in order to prove the generality of the procedure. A number of benchmark instances for all problems are tested using the proposed algorithm in order to prove its effectiveness.     

Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization

An efficient method based on particle swarm optimization (PSO) is developed to solve the Multiprocessor Task Scheduling Problem (MPTSP). To efficiently execute parallelized programs on a multiprocessor environment, a scheduling problem must be solved to determine the assignment of tasks to the processors, the execution order of the tasks, and the starting time of each task, such that some optimality criteria are met. The scheduling problem is known as an NP-complete problem even when the target processors are fully connected and no communication delay is considered among the tasks in the task graph. The complexity of the scheduling problem depends on the number of tasks (N), the number of processors (M), the task processing time and the precedence constraints. The Directed Acyclic Graph (DAG) was exploited to represent the tasks and their precedence constraints. The proposed algorithm was compared with the Genetic Algorithm (GA) and the Duplication Scheduling Heuristic (DSH). We also provide a systematic investigation on the effect of varying problem settings. The results show that the proposed algorithm could not outperform the DSH while it could outperform the GA in some cases.     

基于模拟退火算法的Job Shop问题研究

本文介绍了Metropolis准则,给出了模拟退火算法解决生产调度问题的基本方法和步骤,并对算法的有效性进行了验证。     

网络并行计算中多处理机任务调度问题研究

在网络并行计算系统中,具有多处理机任务需求的多步骤调度是一类常见问题,为此提出一种混合了多处理机任务调度（Multiprocessor Task Scheduling,MTS）和作业车间调度（Job-shop Scheduling Problem,JSP）的调度模型,即多处理机任务作业车间调度（Multiprocessor Task Job-shop Scheduling Problem,MTJSP）。与传统MTS不同的是MTJSP的每项任务的完成都要经历多个步骤。首先对[m]台处理机加工[n]项任务的MTJSP调度问题建立数学模型,然后设计了一种混合粒子群优化（Hybrid Particle Swarm Optimization,HPSO）算法进行求解。算法的改进工作包括：设计出针对多处理机问题的解码策略;采用新的粒子更新方式;增加记忆库功能,以保证全局最优解的多样性;加入基于模拟退火的局部搜索功能。大量的仿真实验验证HPSO的性能,结果显示HPSO不但能够有效解决MTJSP问题,在求解经典JSP问题中也表现优良。     

An integrated production and inventory model for a system comprising an assembly supply chain and a distribution network

This study investigates the production and inventory problem for a system comprising an assembly supply chain and a distribution network. A uniform lot size is produced uninterruptedly with a single setup at each production stage. Equal-sized batch shipment policy is applied to the whole system and the number of batches can be varied. All retailers have agreed on a joint replenishment policy with a common replenishment cycle. The objective is to determine the optimal common replenishment cycle, the number of batches of each production stage and retailer, all of which minimises the integrated total cost. Moreover, a new concept is introduced; namely, critical replenishment cycle. The replenishment cycle division (RCD) and recursive tightening (RT) methods are then developed to obtain the optimal solutions to the subject problem. Two theorems are verified to ensure the solutions obtained by the RCD and RT methods reaching the global optimum. An example is presented to illustrate the procedures involved in the RCD and RT methods.     

Optimization of mixed integer nonlinear economic lot scheduling problem with multiple setups and shelf life using metaheuristic algorithms

This paper addresses the economic lot scheduling problem where multiple items produced on a single facility in a cyclical pattern have shelf life restrictions. A mixed integer non-linear programming model is developed which allows each product to be produced more than once per cycle and backordered. However, production of each item more than one time may result in an infeasible schedule due to the overlapping production times of various items. To eliminate the production time conflicts and to achieve a feasible schedule, the production start time of some or all the items must be adjusted by either advancing or delaying. The objective is to find the optimal production rate, production frequency, cycle time, as well as a feasible manufacturing schedule for the family of items, in addition to minimizing the long-run average cost. Metaheuristic methods such as the genetic algorithm (GA), simulated annealing (SA), particle swarm optimization (PSO), and artificial bee colony (ABC) algorithms are adopted for the optimization procedures. Each of such methods is applied to a set of problem instances taken from literature and the performances are compared against other existing models in the literature. The computational performance and statistical optimization results shows the superiority of the proposed metaheuristic methods with respect to lower total costs compared with other reported procedures in the literature.     

Healthcare service configuration based on project scheduling

Configuration has been recognized as an effective methodology to provide high product variety that caters to individual customer’s needs in the manufacturing industry. For healthcare service configuration, this decision-making process can be taken as service package creation and treated analogously as a project, which is defined as a collection of tasks. This research develops a decision support model to integrate individual patients into the healthcare service configuration process. The healthcare service configuration is formulated as a Resource Constrained Project Scheduling Problem (RCPSP), and a bi-level optimization algorithm based on Genetic Algorithm (GA) is developed for problem solving. The methodology and algorithm are implemented with a case study based on the data obtained from a general hospital in Singapore, which has demonstrated the applicability of healthcare service configuration.