Project time–cost trade-off scheduling: a hybrid optimization approach

This paper develops a hybrid approach for stochastic time–cost trade-off problem (STCTP) in PERT networks of project management, where activities are subjected to linear cost functions. The main objective of proposed approach is to improve the project completion probability in a prespecified deadline from a risky value to a confident predefined probability. To this end, we construct a nonlinear mathematical program with decision variables of activity mean durations, in which the objective function is concerned with minimization of project crashing direct cost. In order to solve the constructed model, we present a hybrid approach based on cutting plane method and Monte Carlo (MC) simulation. To illustrate the process of proposed approach, the approach was coded using MATLAB 7.6.0 and two illustrative examples are discussed. The results obtained from the computational study show that the proposed algorithm is an effective approach for the STCTP.     

基于支持向量机的多目标模糊稳健优化设计

为了提高模糊稳健优化设计的计算效率,探讨了基于支持向量机回归机(SVR)的多目标模糊稳健设计方法,该方法以SVR作为非线性约束函数的替代模型,并采用SVR对模糊概率进行仿真计算,可显著降低模糊稳健优化设计的机时消耗;采用字典序优先级的目标规划法,建立了多目标稳健优化设计模型;把SVR与遗传算法相结合,构建了一种混合智能优化算法;通过多目标稳健设计实例,对所提出的方法进行了验证。     

A mathematical model and ant colony algorithm for multi-manned assembly line balancing problem

In real-world assembly lines, that the size of the product is large (e.g., automotive industry), usually there are multi-manned workstations where a group of workers simultaneously perform different operations on the same individual product. This paper presents a mixed integer programming model to solve the balancing problem of the multi-manned assembly lines optimally. This model minimizes the total number of workers on the line as the first objective and the number of opened multi-manned workstations as the second one. Since this problem is well known as NP (nondeterministic polynomial-time)-hard, a heuristic approach based on the ant colony optimization approach is developed to solve the medium- and large-size scales of this problem. In the proposed algorithm, each ant tries to allocate given tasks to multi-manned workstations in order to build a balancing solution for the assembly line balancing problems by considering the precedence relations, multi-manned assembly line configuration, task times, and cycle time constraints. Through computational experiments, the performance of the proposed ACO is compared with some existing heuristic on various problem instances. The experimental results validate the effectiveness and efficiency of the proposed algorithm.     

Industrial applications of the ant colony optimization algorithm

The ant colony optimization (ACO) algorithm is a fast suboptimal meta-heuristic based on the behavior of a set of ants that communicate through the deposit of pheromone. It involves a node choice probability which is a function of pheromone strength and inter-node distance to construct a path through a node-arc graph. The algorithm allows fast near optimal solutions to be found and is useful in industrial environments where computational resources and time are limited. A hybridization using iterated local search (ILS) is made in this work to the existing heuristic to refine the optimality of the solution. Applications of the ACO algorithm also involve numerous traveling salesperson problem (TSP) instances and benchmark job shop scheduling problems (JSSPs), where the latter employs a simplified ant graph-construction model to minimize the number of edges for which pheromone update should occur, so as to reduce the spatial complexity in problem computation.     

基于支持向量机的模糊稳健优化设计方法

在模糊稳健设计中,需要采用随机模拟方法计算模糊概率和非线性约束函数,但计算效率很低.为此,提出了一种基于支持向量机的模糊稳健设计方法.采用支持向量回归机对模糊概率进行仿真计算,采用支持向量回归机或分类机作为非线性约束函数的替代模型,显著降低了模糊稳健优化设计的机时消耗.给出了新方法的具体算法步骤,并通过模糊稳健优化设计...     

The two-stage assembly flowshop scheduling problem with bicriteria of makespan and mean completion time

In this paper, we address the two-stage assembly flowshop scheduling problem with a weighted sum of makespan and mean completion time criteria, known as bicriteria. Since the problem is NP-hard, we propose heuristics to solve the problem. Specifically, we propose three heuristics; simulated annealing (SA), ant colony optimization (ACO), and self-adaptive differential evolution (SDE). We have conducted computational experiments to compare the performance of the proposed heuristics. It is statistically shown that both SA and SDE perform better than ACO. Moreover, the experiments reveal that SA, in general, performs better than SDE, while SA consumes less CPU time than both SDE and ACO. Therefore, SA is shown to be the best heuristic for the problem.     

An ant colony algorithm for scheduling in flowshops with sequence-dependent setup times of jobs

The problem of scheduling in flowshops with sequence-dependent setup times of jobs is considered and solved by making use of ant colony optimization (ACO) algorithms. ACO is an algorithmic approach, inspired by the foraging behavior of real ants, that can be applied to the solution of combinatorial optimization problems. A new ant colony algorithm has been developed in this paper to solve the flowshop scheduling problem with the consideration of sequence-dependent setup times of jobs. The objective is to minimize the makespan. Artificial ants are used to construct solutions for flowshop scheduling problems, and the solutions are subsequently improved by a local search procedure. An existing ant colony algorithm and the proposed ant colony algorithm were compared with two existing heuristics. It was found after extensive computational investigation that the proposed ant colony algorithm gives promising and better results, as compared to those solutions given by the existing ant colony algorithm and the existing heuristics, for the flowshop scheduling problem under study.     

A new fuzzy group multi-criteria decision making method with an application to the critical path selection

In this paper, we propose a new fuzzy group multi-criteria decision making method and apply it to determine the critical path in a project network. The criteria used here are time (expected duration), cost, risk, and quality of the project activities that are considered critical in project management. As each criterion has its independent level of importance in the critical path selection, the weights of the project criteria are also considered in the analysis. Considering that the information in terms of various project activities and criteria weights are often incomplete and/or uncertain in real-world situations, the essential information in terms of the criteria and project activities are obtained using triangular fuzzy numbers and/or linguistic variables that are mapped to triangular fuzzy numbers, wherever appropriate. The proposed method involves fuzzy evaluation based on the fuzzy information of the possible project paths on each criterion leading to the strength and weakness index scores of the project paths. We define a measure of criticality termed as the total performance score of each project path obtained using its strength and weakness index scores. The path that has the highest measure of criticality is selected as the critical path. A numerical illustration is provided to demonstrate working of the proposed methodology. Further, a case study from manufacturing engineering industry is also presented to better justify the applicability and potentials of the proposed methodology. A comparison with closely related fuzzy multi-criteria decision methods for the critical path selection is done to analyze the performance of the proposed methodology.     

Computer simulation machining a 3D free surface by using a 3-RPRU parallel machine tool

A novel computer aided geometric approach is proposed to machine a 3D free surface by adopting a 3-RPRU parallel machine tool. Based on the geometry constraint and dimension-driving technique, a 3-RPRU parallel simulation mechanism is first created. Next, a 3D free surface and a guiding plane of tool path are constituted. Finally, the 3-RPRU parallel simulation mechanism, the 3D free surface, and the guiding plane of the tool path are combined together, and a novel 3-RPRU simulation parallel machine tool is created for machining a 3D free surface. In the light of two specified tool paths, the extension of the three driving rods and the position of the moving platform are solved and visualized dynamically. Based on the computer simulation results, some analytic formulas are derived to solve the extension of driving rods of the 3-RPRU parallel machine tool in a reverse solving process. From the simulation and analytic results, it is proven that the computer simulation machine tool approach is equivalent to the analytic approach to machine 3D free surfaces. The computer simulation machine tool approach is straightforward without compiling computer programs, and is also advantageous from the viewpoint of accuracy and repeatability. This project is supported by NSFC 50575198.     

用双向收敛蚁群算法解作业车间调度问题

为了合理高效地调度资源，解决组合优化问题，在Job-Shop问题图形化定义的基础上，借鉴精英策略的思路，提出使用多种挥发方式的双向收敛蚁群算法，提高了算法的效率和可用性。最后，通过解决基准问题的实验，比较了双向收敛蚁群和蚁群算法的性能。实验结果表明，在不明显影响时间、空间复杂度的情况下，双向收敛蚁群算法可以加快收敛速度。     

一种新型蚁群随机树的机器人路径规划算法

为提高复杂环境下机器人的路径规划效率,提出了一种用蚁群算法来优化随机树算法的新的全局路径规划算法。该算法有效地结合了蚁群和随机树算法的优点,利用随机树算法的高效性快速收敛到一条可行路径,将该路径转换为蚁群的初始信息素分布,可以减少蚁群算法初期迭代; 然后利用蚁群算法的反馈性优化路径,求得最优路径。仿真实验表明,该蚁群随机树算法可以提高机器人路径规划的速度,并且在任何复杂环境下迅速规划出最优路径。     

A discrete-event simulation approach with multiple-comparison procedure for stochastic resource-constrained project scheduling

Aiming to minimize the average project duration, a discrete-event simulation (DES) approach with multiple-comparison procedure is presented to solve the stochastic resource-constrained project scheduling problem (SRCPSP). The simulation model of SRCPSP is composed of a resource management model and a project process model, where the resource management model is used to administrate resources of the project, and the project process model based on an extended-directed-graph is proposed to describe the precedence constraints and resource constraints in SRCPSP. A simplified simulation strategy based on activity scanning method is used in the simulation model to generate feasible schedules of the problem. A multiple-comparison procedure based on the common random numbers is adopted to compare the multiple scheduling alternatives obtained from the stochastic simulation model and provide more information to select the optimal scheduling alternative. The cases are given to compare with other methods for the same SRCPSP from literature and show that the simulation tool by utilizing DES with a statistical method improves the efficiency of simulation in stochastic project planning.     

VIRTUAL PROCESSING OF LASER SURFACE HARDENING ON AUTOBODY DIES

A new method of collision-free path plan integrated in virtual processing is developed to improve the efficiency of laser surface hardening on dies. The path plan is based on the premise of no collision and the optimization object is the shortest path. The optimization model of collision-free path is built from traveling salesman problem (TSP). Collision-free path between two machining points is calculated in configuration space (C-Space). Ant colony optimization (ACO) algorithm is applied to TSP of all the machining points to fmd the shortest path, which is simulated in virtual environment set up by IGRIP software. Virtual machining time, no-collision report, etc, are put out after the simulation. An example on autobody die is processed in the virtual platform, the simulation results display that ACO has perfect optimization effect, and the method of virtual processing with integration of collision-free optimal path is practical.     

CAPACITATED LOT SIZING AND SCHEDULING PROBLEMS USING HYBRID GA／TS APPROACHES

The capacitated lot sizing and scheduling probbm that involves in determining the production amounts and release dates for several items over a given planning horizon are given to meet dynamic order demand without incurring backloggings. Thi: problem considering overtime capacity is studied. The mathematical model is presented, and a genelic algorithm (GA) approach is developed to solve the problem. The initial solutions are generated after using heuristic method. Capacity balancing procedure is employed to stipulate the feasibility of the solutions. In addition, a technique based on Tabu search (TS) is inserted into the genetic algorithm to d;al with the scheduled overtime and help the convergence of algorithm. Computational simulation is conducted to test the efficiency of the proposed hybrid approach, which turns out to improve both the solution quality and execution speed.     

Sequencing and scheduling of job and tool in a flexible manufacturing system using ant colony optimization algorithm

Many optimization problems from the manufacturing systems are very complex in nature and quite hard to solve by conventional optimization techniques. The theme of this paper is to generate an active schedules and optimal sequence of job and tool that can meet minimum makespan schedule for the flexible manufacturing system. It consists of similar work center which is capable of doing many operations. The tools are stored in a common tool magazine that shares with and serves for several work centers to reduce the cost of duplicating tools in each and every work center. This type of manufacturing system is used for a manufacturing environment in which tools are expensive. To achieve the objective, the jobs and tools are sequenced and scheduled. In this work, non-traditional optimization technique such as ant colony optimization (ACO) algorithm are proposed to derive near-optimal solutions which adopt the Extended Giffler and Thompson algorithm for active feasible schedule generation. In this paper, the proposed algorithm is used for solving number of problems taken from the literature. The results available for the various existing algorithms are compared with results obtained by the ACO algorithm. The analysis reveals that ACO algorithm provides better solution with reasonable computational time.     

地铁车辆电动塞拉门的剩余寿命预测

针对地铁车辆客室电动塞拉门传动装置润滑不良的问题,提出了基于自组织映射（SOM）神经网络、隐马尔可夫链（HMC）模型和蒙特卡罗（MC）仿真的剩余使用寿命预测方法。该方法首先对采集到的电机电流信号进行特征提取;然后利用SOM对提取出的多维特征数据进行融合与编码,将所得结果作为HMC的输入向量,训练得到全部寿命下劣化状态转移矩阵;最后利用MC方法实现对其劣化过程的剩余使用寿命预测。故障模拟实验结果表明,该方法可以在考虑润滑不良故障模式下,有效预测得到电动塞拉门丝杆的剩余使用寿命。     

基于改进蚁群算法的汽车混流装配调度模型求解

针对某汽车总装车间混流装配过程涉及大量人工以及人机协同操作而导致工位过载、整车装配质量无法得到保证的问题,建立了瓶颈选装工位负载平衡化、考虑换装与提前作业时间的加工滞后次数最小化的分层序列双目标优化模型,同时设计了一种改进蚁群算法。该算法在信息素全局更新以及概率转移规则过程中,使用一种特定启发式函数,并更改迭代过程中最优解的评价方法。仿真对比实验结果表明,该算法在优化目标函数过程中的收敛速度、收敛精度、最优解质量等方面均优于传统蚁群算法和对比遗传算法,验证了模型和算法的有效性。此外,该算法还可反向求解加工滞后次数为零时的计划生产节拍,具有一定的生产指导意义。     

Hybrid meta-heuristic algorithm for job shop scheduling with due date time window and release time

This study intends to solve the job shop scheduling problem with both due data time window and release time. The objective is to minimize the sum of earliness time and tardiness time in order to reduce the storage cost and enhance the customer satisfaction. A novel hybrid meta-heuristic which combines ant colony optimization (ACO) and particle swarm optimization (PSO), called ant colony–particle swarm optimization (ACPSO), is proposed to solve this problem. Computational results indicate that ACPSO performs better than ACO and PSO.     

Hybrid approach to distribution planning reflecting a stochastic supply chain

Today’s business environment is experiencing as a period of expansion and the globalization. Therefore, a distribution plan with low cost and high customer satisfaction in supply chain management (SCM) has been widely investigated. The purpose of this study is to establish optimal distribution planning in the supply chain. In this paper, a hybrid approach involving a genetic algorithm (GA) and simulation is presented to solve this problem. The GA is employed in order to quickly generate feasible distribution sequences. Considering uncertain factors such as queuing, breakdowns and repairing time in the supply chain, the simulation is used to minimize completion time for the distribution plan. The computational results for an example of a simple supply chain are given and discussed to validate the proposed approach. We obtained a more realistic distribution plan with optimal completion time by performing the iterative hybrid GA simulation procedure which reflects the stochastic nature of supply chains.     

Incomplete mesh-based tool path generation for optimum zigzag milling

The majority of mechanical parts are manufactured by milling machines. Hence, geometrically efficient algorithms for tool path generation and physical considerations for better machining productivity with guarantee of machining safety are the most important issues in milling tasks. In this paper, we present an optimized path-generation algorithm for zigzag milling, which is commonly used in the roughing stage as well as in the finishing stage, based on an incomplete two-manifold mesh model, namely, an inexact polyhedron that is widely used in recent commercialized CAM software systems. First of all, a geometrically efficient tool path generation algorithm using an intersection points-graph is introduced. Although the tool path obtained from geometric information has been successful to make a desirable shape, it seldom considers physical process concerns like cutting forces and chatter. In order to cope with these problems, an optimized tool path that maintains constant MRR in order to achieve constant cutting forces and to avoid chatter vibrations at all times is introduced and the result is verified. Additional tool path segments are appended to the basic tool path by using a pixel-based simulation technique. The algorithm was implemented for two-dimensional contiguous end-milling operations with flat end mills and cutting tests were conducted by measuring the spindle current, (which reflect machining situations) to verify the significance of the proposed method.