Table of Content

25 November 2018, Volume 29 Issue 22

Previous Issue    Next Issue

MILP Models and an Improved BSA for Hybrid Flow Shop Scheduling Problems with Blocking

MENG Leilei, ZHANG Chaoyong, REN Caile, LI Zhenguo, REN Yaping

2018, 29(22):  2647-2658. 

Asbtract ( )   PDF (756KB) ( )  

References | Related Articles | Metrics

The hybrid flow shop scheduling problems with blocking(HFSP-B) were studied with the minimization of makespans. Firstly, four MILP models were proposed based on different modeling ideas. Secondly, due to the inefficiency of the MILP model to medium-large problems, an improved backtracking search optimization algorithm(IBSA) was proposed. In this algorithm, roulette selection strategy and VNS were introduced to improve the convergence rate and local search ability. At last, numerical experiments were completed on real instances and the results show the effectiveness and superiority of the proposed MILP models and the IBSA.

Multi-Agent Job Shop Scheduling Strategy Based on Pheromone

CHEN Ming, ZHU Haihua, ZHANG Zequn, JIN Yongqiao, WANG Yingcong, TANG Dunbing

2018, 29(22):  2659-2665. 

Asbtract ( )   PDF (544KB) ( )  

References | Related Articles | Metrics

Aiming at the disadvantages of traditional multi-Agent methods based on contractual network protocol,such as single target optimization,large communication volumes,and poor global performance optimization,a multi-Agent dynamic scheduling strategy was proposed based on pheromone.The strategy achieved indirect negotiation between Agents by pheromone, reduced traffic and realied global multi-objective optimization.In addition,the task allocation stages and buffer job selection stages were optimized at the same time.The independent setup time was taken into account,which was more practical and further improved the overall system optimization effectiveness.Finally,an example simulation was used to verifiy the efficiency of the strategy.

Model and Algorithm of Paravlel Multiprocessor Open Shop Scheduling Problem

CHEN YarongHUANG PeiyuLI PeiCHOU FuhderHUANG Shengquan

2018, 29(22):  2666-2673,2681. 

Asbtract ( )   PDF (613KB) ( )  

References | Related Articles | Metrics

Grain sorting scheduling problem in LED manufacturing was a typical multiprocessor open shop scheduling problem，which belonged to NP-hard problem.Model and algorithm for solving this kind of scheduling problems with the objective of minimizing total weighted completion time were studied herein.According to the characteristics of the problem，a mixed integer-programming model was constructed to obtain the optimal solution，and a heuristic algorithm and an improved particle swarm optimization algorithm were designed.Simulation results show that both heuristic algorithm and improved particle swarm optimization algorithm may obtain good scheduling solutions quickly and effectively in a reasonable time.

HCS Algorithm for Multi-objective Flow Shop Scheduling Problems with Energy Consumption

ZHONG Lingchong, QIAN Bin, HU Rong, WANG Ling

2018, 29(22):  2674-2681. 

Asbtract ( )   PDF (595KB) ( )  

References | Related Articles | Metrics

To consider the economic and environmental factors at the same time, this paper dealt with the multi-objective permutation flow shop scheduling problems (MOPFSP) which minimized make-span and total carbon emissions. MOPFSP was proved to be a NP-hard problem for more than two machines. A HCS algorithm was proposed to solve the problems. Firstly, a largest-order-value rule was utilized to transform HCSs individuals from real vectors to job permutations so that HCS might be used to perform search in MOPFSPs solution spaces. Secondly, an adapive factor of step size was designed to control the search scopes in the evolution phases. Thirdly, a multi-neighborhood local search was presented to exploit the excellent subregions obtained by HCSs global search. Due to the hybridization of CS-based global search and multi-neighborhood local search, MOPFSP may be solved efficiently. Simulations and comparisons verify the efficiency of HCS to solve MOPFSP.

A Novel Shuffled Frog-leaping Algorithm for FJSP withTotal Energy Consumption Constraints

YANG Dongjing, LEI Deming

2018, 29(22):  2682-2689. 

Asbtract ( )   PDF (530KB) ( )  

References | Related Articles | Metrics

To solve the flexible job shop scheduling problem (FJSP) with total energy consumption constraints and the objective of total tardiness,the problem was transformed into the bi-objective FJSP with objectives of total energy consumption and total tardiness to effectively deal with energy consumption constraints,and then a novel shuffled frog leaping algorithm was proposed to directly optimize the transformed FJSP. Some new methods were used to improve the solution qualities,which were the new strategies of memeplex construction and memeplex search,and the reinforced search of the best solution in memeplex. The computational experiments and the result analyses show that the novel algorithm has a strong search ability to solve the considered problems.

Genetic Evalution Method for JSP under Mixed Work Calendars

ZENG Qiang, DENG Jingyuan, CHANG Menghui, ZHANG Jinchun

2018, 29(22):  2690-2702. 

Asbtract ( )   PDF (802KB) ( )  

References | Related Articles | Metrics

A genetic evolution method was presented to solve a kind of JSP under mixed work calendars. Firstly，a job shop scheduling optimization model was established under mixed work calendars to minimize production cycle. Secondly，a time reckoning method was proposed based on work calendar,and a GA was designed to solve the problems above. The process-based encoding method was used to encode chromosomes. An improved strategy of genetic operators was used in genetic operations to ensure feasibility of chromosomes and reduce calculation amounts. In decoding operation，the proposed time reckoning method was used to calculate start time and end time of each operation accurately based on the work calendar，and two techniques were adopted to shorten production cycle.Finally，application results show that the proposed method may solve the JSP under mixed work calendars effectively.

An Improved Ant Colony Algorithm for Solving Single Machine Total Weighted Delay Scheduling Problem

QIAO Dongping, PEI Jie, WEN Xiaoyu, XIAO Yanqiu, JIAO Jianqiang,

2018, 29(22):  2703-2710. 

Asbtract ( )   PDF (566KB) ( )  

References | Related Articles | Metrics

A single machine scheduling problem under minimized total weighted tardiness was studied, and an improved ant colony algorithm was proposed herein based on pheromone updating differently. The algorithm used a coding method which was based on job sequence, and improved the setting of heuristic information by priority rule of modified due date. The pheromone between nodes was updated adaptively and differently by the positive and negative feedback mechanism. A pairwise exchange strategy was used for local search to further improve the quality of scheduling scheme. Finally, simulations on multiple benchmark instances in OR-Library show that the proposed algorithm is feasible and effective.

Assembly Line Balancing Problem of  Type Ⅱ Based on Fruit Fly Algorithm

DU Lizhen, WANG Yunfa, WANG Zhen, YU Lianqing, LI Xinyu

2018, 29(22):  2711-2715. 

Asbtract ( )   PDF (426KB) ( )  

References | Related Articles | Metrics

Based on the characteristics of assembly line balancing problem of type Ⅱ, a multi-objective research model was established. A method of fruit fly algorithm was used to solve the benchmark cases, and the simulation research was carried out by MATLAB. The results gained from the fruit fly algorithm were compared with that of the adaptive genetic algorithm for solving the same benchmark cases, it was obvious that cycle time was reduced, assembly line balancing was improved, and workload of the stations became more balanced. Then the availability of the fruit fly algorithm for solving the assembly line balancing problem of type Ⅱ  was proved that the global optimal solutions have more strong ability.

Two-stage Hybrid Algorithm for Integrated Process Planning and Scheduling Problems

WEN Xiaoyu, LUO Guofu, LI Hao, XIAO Yanqiu, QIAO Dongping

2018, 29(22):  2716-2724,2732. 

Asbtract ( )   PDF (680KB) ( )  

References | Related Articles | Metrics

A two-stage hybrid algorithm was designed for solving integrated process planning and scheduling problems. In process planning stage,genetic algorithm was utilized to generate alternative near-optimal process plan sets for each job. The alternative near-optimal process plan sets were used to input special process plans of jobs to job shop scheduling stage dynamically.In job shop scheduling processes,honey bees mating optimization algorithm was employed for searching the optimal solution effectively. Queens mating flight processes were designed to guarantee the global search capability of the proposed algorithm,while workers were constructed as local search strategies to improve the broods  based on different neighborhood structures. Benchmark instances were used to evaluate the performance of the proposed algorithm. The comparisons with other algorithms were also presented,which verified the effectiveness of the proposed method.

Time Node Prediction Method for Material Delivery Based on Information Entropy

REN Yinghui, HUANG Xiangming, MA Zhongkai, ZHOU Zhixiong

2018, 29(22):  2725-2732. 

Asbtract ( )   PDF (517KB) ( )  

References | Related Articles | Metrics

Aiming at the problems that the uncertain disturbance factors affect the material distribution time node in complex product assembly shops, a novel forecasting method was proposed to schedule material distribution time node ground on information entropy analysis. The types of uncertain disturbance factors in the complex product assembly lines were defined and quantified by the integrated time requirement factors,and the status of assembly station was defined. Then the state transition probability matrix was also established. The forecasting model of material distribution time node was built, which related with the Markov chain characteristics of station state transition for complex product assembly workshops.A dynamic error compensation method was utilized to amend the initial prediction values through calculating average prediction errors. An evaluation system was constructed to evaluate the forecasting results using information entropy, that the maximum delivery feasibility time and distribution accuracy were selected as the evaluation index. Finally, the forecasting method was validated by an example of a companys grinding machine spindle assembly station. The results show that the method has a significant effect on increasing the feasibility of the maximum distribution and improving the accuracy of the material distribution time.

Feature Extraction for Map Building of Automated Guided Robot Based on Laser Navigation without Reflector

LI Danyang, ZHANG Ke, XU Ruqing, LUO Zhifeng, WU Jiaqian, GUI Hao,

2018, 29(22):  2733-2739. 

Asbtract ( )   PDF (751KB) ( )  

References | Related Articles | Metrics

To realize the line feature extraction of map building for laser navigation robot without reflector，a stepwise decomposition method was proposed herein.The line feature extraction method was divided into 3 steps: breakpoint detection，line segmentation，and line extraction.Firstly，an adaptive threshold method was used to detect the breakpoints.And then，a point set was separated，and the line segment was segmented based on the iterative adaptive point algorithm.Finally，a least square method was used to fit the lines，and the region search method was used to optimize the line feature extraction.Experiments show that the repetitive positioning accuracy of the algorithm is within ±6mm and the feature extraction time is not longer than 0.02s，which meets the actual navigation requirements of robots.

An Adaptive Parallel Genetic Algorithm for VRPSPD

ZHOU Rong, SHEN Weilei

2018, 29(22):  2740-2749. 

Asbtract ( )   PDF (678KB) ( )  

References | Related Articles | Metrics

Considering both of  dispatching costs of vehicles and travelling costs of routes，a mixed integer mathematical formulation of the VRPSPD was established to make the total delivery costs，the number of vehicles and the travel costs minimize simultaneously. An adaptive parallel genetic algorithm was proposed for solving the VRPSPD. Inspired by the C-W saving algorithm，three heuristic methods with two kinds of demands for initializing population were presented to reduce the search scopes and optimize the initial solutions. A bi-group parallel strategy with diversity population and high quality population was proposed to realize the synchronous search of depth and breadth. The adaptive genetic operations of crossover and mutation were applied to improve the stagnation of the search in high quality population. And based on a kind of special mutation a post-optimization was carried out for the global best individuals to further improve the global optimal performance. The feasibility and effectiveness of the proposed algorithm were verified by two instances based on standard dataset.

Supply Chain Scheduling under Time-of-use Electricity Tariffs and Time-dependent Travel Times

WANG Jun

2018, 29(22):  2750-2757. 

Asbtract ( )   PDF (526KB) ( )  

References | Related Articles | Metrics

A single-machine supply chain scheduling problem was studied with the consideration of time-of-use electricity tariffs in production planning stages and time-dependent travel times in batch delivery phases.A mixed integer programming model was presented with the objective to minimize the total costs. By analyzing the model, properties of the optimal solution were proposed, and the model was decomposed into several batches which were machine scheduling sub-problems. For the optimization of sub-problems, a subset partitioning heuristic algorithm was designed, and optimization of the algorithm was proved.An adaptive variable neighborhood search algorithm was designed for the main problem optimization. The computational results verify the effectiveness of the model and algorithm, and show that the supply chain integrated scheduling may reduce energy consumption.

Multi-objective Optimization Method of Product Development Task Scheduling Based on NSGA-Ⅱ

TIAN Qihua, MING Wenhao, WEN Xiaoyong, DU Yixian, ZHOU Xiangman

2018, 29(22):  2758-2766. 

Asbtract ( )   PDF (772KB) ( )  

References | Related Articles | Metrics

Traditional weighted coefficient method and constraint method could not solve the problems of multi-objective optimization of product development task scheduling very well, a multi-objective optimization model was established with the goals of product development time and expenses. A Pareto optimal solution set was obtained by applying NSGA-Ⅱ.This solution set was selected by using fuzzy optimum seeking method, and the optimal implementation plan of product development task scheduling was determined.Superiority of the algorithm was proved by the solutions and comparative analyses of two classical multi-objective test functions. An example was given to illustrate the implementation processes and the effectiveness of the method.

Collaborative Optimization of Dynamic Manufacturing Production Planning and Scheduling

WANG Yanhong, YU Ning, CAI Ming, XING Dawei

2018, 29(22):  2767-2771. 

Asbtract ( )   PDF (471KB) ( )  

References | Related Articles | Metrics

Based on the idea of collaborative optimization of production planning and scheduling，a rolling optimization model of planning and scheduling was established，and a “closed-loop integration - rolling rescheduling” strategy was proposed. When the production system had dynamic changes such as capacity constraints or order changes，the scheduling and planning formed a “closed-loop response mode”，and further used the dynamic constraint balancing hybrid algorithm to optimize the production planning and scheduling. In order to verify the effectiveness and feasibility of the proposed cooperative optimization strategy，a typical example was selected for simulation. The results show that the strategy may effectively deal with the dynamic changes of the production system，and ensure the timely adjustment of the system scheduling optimization.