Minimizing Total Tardiness in a Two-Machine Flowshop Scheduling Problem with Availability Constraints

In this paper,we consider the problem of minimizing the total tardiness in a deterministic two-machine permutationflowshop scheduling problem subject to release dates of jobs and known unavailability periods of machines.The theoretical and practical importance of minimizing tardiness inflowshop scheduling environment has motivated us to investigate and solve this interested two-machine scheduling problem.Methods that solve this important optimality criterion inflowshop environment are mainly heuristics.In fact,despite the N P-hardnessin the strong sense of the studied problem,to the best of our knowledge there are no approximate algorithms(constructive heuristics or metaheuristics)or an algorithm with worst case behavior bounds proposed to solve this problem.Thus,the design of new promising algorithms is desirable.We developfive metaheuristics for the problem under consideration.These metaheuristics are:the Particle Swarm Optimization(PSO),the Differential Evolution(DE),the Genetic Algorithm(GA),the Ant Colony Optimization(ACO)and the Imperialist Competitive Algorithm(ICA).All the proposed metaheuristics are population-based approaches.These metaheuristics have been improved by integrating different local search procedures in order to provide more satisfactory,especially in term of quality solutions.Computational experiments carried out on a large set of randomly generated instances provide evidence that the Imperialist Competitive Algorithm(ICA)records the best performances.

HEURISTIC STUDY OF FLOWSHOP SCHEDULING TO MINIMIZE MEAN FLOW TIME WITH LOT TRANSFER CONSIDERED

Lot scheduling problem with idle time transfer between processes to minimize mean flow time is very important because to minimize mean flow time is to minimize work in process. But the problem is NP hard and no polynomial algorithm exists to guarantee optimal solution. Based the analysis the mathematical structure of the problem, the paper presents a new heuristic algorithm. Computer simulation shows that the proposed heuristic algorithm performs well in terms of both quality of solution and execution speed.

Tabu search for no-wait flowshop scheduling problem to minimize maximum lateness

In order to solve the no-wait flowshop scheduling problem to minimize the maximum lateness,three job-block-based neighborhoods are proposed,among which the block exchange neighborhood have a size of O（n4）while the block swap and the simplified block exchange neighborhoods have a size of O（n3）.With larger sizes than the existing neighborhoods,the proposed neighborhoods can enhance the solution quality of local search algorithms.Speedup properties for the neighborhoods are developed,which can evaluate a neighbor in constant time and explore the neighborhoods in time proportional to their proposed sizes. Unlike the dominance-rule-based speedup method,the proposed speedups are applicable to any machine number.Three neighborhoods and the union of block swap and the simplified block exchange neighborhoods are compared in the tabu search.Computational results on benchmark instances show that three tabu search algorithms with O（n3）neighborhoods outperform the existing algorithms and the tabu search algorithm with the union has the best performance among all the tested algorithms.

Hybrid artificial immune system and extremal optimization algorithm for permutation flowshop scheduling problem

The permutation flowshop scheduling problem （PFSP） is one of the most well-known and well-studied production scheduling problems with strong industrial background. This paper presents a new hybrid optimization algorithm which combines the strong global search ability of artificial immune system （AIS） with a strong local search ability of extremal optimization （EO） algorithm. The proposed algorithm is applied to a set of benchmark problems with a makespan criterion. Performance of the algorithm is evaluated. Comparison results indicate that this new method is an effective and competitive approach to the PFSP.

A hybrid two-stage fexible flowshop scheduling problem with m identical parallel machines and a burn-in processor separately

A hybrid two-stage flowshop scheduling problem was considered which involves m identical parallel machines at Stage 1 and a burn-in processor M at Stage 2, and the makespan was taken as the minimization objective. This scheduling problem is NP-hard in general. We divide it into eight subcases. Except for the following two subcases： （1） b≥ an, max{m, B} 〈 n; （2） a1 ≤ b ≤ an, m ≤ B 〈 n, for all other subcases, their NP-hardness was proved or pointed out, corresponding approximation algorithms were conducted and their worst-case performances were estimated. In all these approximation algorithms, the Multifit and PTAS algorithms were respectively used, as the jobs were scheduled in m identical parallel machines.

A Branch-and-Bound Based Heuristic Algorithm for Minimizing Makespan in Machining-Assembly Flowshop Scheduling

This paper proposes a heuristic algorithm, called list-based squeezing branch and bound algorithm, for solving a machine-fixed, machining-assembly flowshop scheduling problem to minimize makespan. The machine-fixed, machining-assembly flowshop consists of some parallel two-machine flow lines at a machining stage and one robot at an assembly stage. Since an optimal schedule for this problem is not always a permutation schedule, the proposed algorithm first finds a promising permutation schedule, and then searches better non-permutation schedules near the promising permutation schedule in an enumerative manner by elaborating a branching procedure in a branch and bound algorithm. The results of numerical experiments show that the proposed algorithm can efficiently provide an optimal or a near-optimal schedule with high accuracy such as mean relative error being less than 0.2% and the maximum relative error being at most 3%.

A Genetic Algorithm for the Flowshop Scheduling Problem

The flowshop scheduling problem is NP complete. To solve it by genetic algorithm, an efficient crossover operator is designed. Compared with another crossover operator, this one often finds a better solution within the same time.

A Heuristic Algorithm for the Two-Machine Flowshop Group Scheduling Problem

This paper presents the two-machine flowshop group scheduling problem with the optimal objective of maximum lateness. A dominance rule within group and a dominance rule between groups are established. These dominance rules along with a previously established dominance rule are used to develop a heuristic algorithm. Experimental results are given and analyzed.

A Heuristic Genetic Algorithm for No-Wait Flowshop Scheduling Problem

No-wait flowshop scheduling problems with the objective to minimize the total flow time is an important se-quencing problem in the field of developing production plans and has a wide engineering background. Genetic algo-rithm (GA) has the capability of global convergence and has been proven effective to solve NP-hard combinatorial op-timization problems,while simple heuristics have the advantage of fast local convergence and can be easily imple-mented. In order to avoid the defect of slow convergence or premature,a heuristic genetic algorithm is proposed by in-corporating the simple heuristics and local search into the traditional genetic algorithm. In this hybridized algorithm,the structural information of no-wait flowshops and high-effective heuristics are incorporated to design a new method for generating initial generation and a new crossover operator. The computational results show the developed heuristic ge-netic algorithm is efficient and the quality of its solution has advantage over the best known algorithm. It is suitable for solving the large scale practical problems and lays a foundation for the application of meta-heuristic algorithms in in-dustrial production.

Algorithms for Assembly Type Flowshop Scheduling Problem

An assembly type flowshop scheduling problem with minimizing makespan is considered in this paper. The problem of scheduling for minimizing makespan is first addressed, and then a new heuristic algorithm is proposed for it.

An improved artificial bee colony algorithm for steelmaking–refining–continuous casting scheduling problem

Steelmaking–refining–Continuous Casting(SCC) scheduling is a worldwide problem, which is NP-hard. Effective SCC scheduling algorithms can help to enhance productivity, and thus make significant monetary savings. This paper develops an Improved Artificial Bee Colony(IABC) algorithm for the SCC scheduling. In the proposed IABC, charge permutation is employed to represent the solutions. In the population initialization, several solutions with certain quality are produced by a heuristic while others are generated randomly. Two variable neighborhood search neighborhood operators are devised to generate new high-quality solutions for the employed bee and onlooker bee phases, respectively. Meanwhile, in order to enhance the exploitation ability, a control parameter is introduced to conduct the search of onlooker bee phase. Moreover, to enhance the exploration ability,the new generated solutions are accepted with a control acceptance criterion. In the scout bee phase, the solution corresponding to a scout bee is updated by performing three swap operators and three insert operators with equal probability. Computational comparisons against several recent algorithms and a state-of-the-art SCC scheduling algorithm have demonstrated the strength and superiority of the IABC.

Improved Fruit Fly Optimization Algorithm for Solving Lot-Streaming Flow-Shop Scheduling Problem

An improved fruit fly optimization algorithm( iFOA) is proposed for solving the lot-streaming flow-shop scheduling problem( LSFSP) with equal-size sub-lots. In the proposed iFOA,a solution is encoded as two vectors to determine the splitting of jobs and the sequence of the sub-lots simultaneously. Based on the encoding scheme,three kinds of neighborhoods are developed for generating new solutions. To well balance the exploitation and exploration,two main search procedures are designed within the evolutionary search framework of the iFOA,including the neighborhood-based search( smell-vision-based search) and the global cooperation-based search. Finally,numerical testing results are provided,and the comparisons demonstrate the effectiveness of the proposed iFOA for solving the LSFSP.

Multi-objective reconfigurable production line scheduling for smart home appliances

In a typical discrete manufacturing process,a new type of reconfigurable production line is introduced,which aims to help small-and mid-size enterprises to improve machine utilization and reduce production cost.In order to effectively handle the production scheduling problem for the manufacturing system,an improved multi-objective particle swarm optimization algorithm based on Brownian motion(MOPSO-BM)is proposed.Since the existing MOPSO algorithms are easily stuck in the local optimum,the global search ability of the proposed method is enhanced based on the random motion mechanism of the BM.To further strengthen the global search capacity,a strategy of fitting the inertia weight with the piecewise Gaussian cumulative distribution function(GCDF)is included,which helps to maintain an excellent convergence rate of the algorithm.Based on the commonly used indicators generational distance(GD)and hypervolume(HV),we compare the MOPSO-BM with several other latest algorithms on the benchmark functions,and it shows a better overall performance.Furthermore,for a real reconfigurable production line of smart home appliances,three algorithms,namely non-dominated sorting genetic algorithm-II(NSGA-II),decomposition-based MOPSO(dMOPSO)and MOPSO-BM,are applied to tackle the scheduling problem.It is demonstrated that MOPSO-BM outperforms the others in terms of convergence rate and quality of solutions.

Flow-Shop Scheduling with Transportation Capacity and Time Consideration

Planning and scheduling is one of the most important activity in supply chain operation management.Over the years,there have been multiple researches regarding planning and scheduling which are applied to improve a variety of supply chains.This includes two commonly used methods which are mathematical programming models and heuristics algorithms.Flowshop manufacturing systems are seen normally in industrial environments but few have considered certain constraints such as transportation capacity and transportation time within their supply chain.A two-stage flowshop of a single processing machine and a batch processing machine are considered with their capacity and transportation time between twomachines.The objectives of this research are to build a suitable mathematical model capable of minimizing the maximum completion time,to propose a heuristic optimization algorithm to solve the problem,and to develop an applicable program of the heuristics algorithm.AMixed Integer Programming(MIP)model and a heuristics optimization algorithmwas developed and tested using a randomly generated data set for feasibility.The overall results and performance of each approach was compared between the two methods that would assist the decision maker in choosing a suitable solution for their manufacturing line.

Sensitivity analysis for some scheduling problems

This paper gives the sensitivity analysis for some scheduling problems, including the following： what are the limits to a parameter change such that the solution remain optimal？ Given a specific change of a parameter, what is the new optimal cost？ Given a specific change of a parameter, what is a new optimal solution？ Here, the concern is mainly with the sensitivity analysis for some single-machine and flowshop scheduling problems with polynomial time algorithms. It is shown that, for these problems, the sensitivity analysis results depend on the positions of jobs with changed parameters.

Greedy Constructive Procedure-Based Hybrid Differential Algorithm for Flexible Flow shop Group Scheduling

Aiming at the flexible flowshop group scheduling problem,taking sequence dependent setup time and machine skipping into account, a mathematical model for minimizing makespan is established,and a hybrid differential evolution( HDE) algorithm based on greedy constructive procedure( GCP) is proposed,which combines differential evolution( DE) with tabu search( TS). DE is applied to generating the elite individuals of population,while TS is used for finding the optimal value by making perturbation in selected elite individuals. A lower bounding technique is developed to evaluate the quality of proposed algorithm. Experimental results verify the effectiveness and feasibility of proposed algorithm.

分布式装配置换流水车间调度问题研究综述

近几十年来,现代制造业发展迅速,一种趋势是在分布式生产工厂进行工件的加工,待完成后到装配工厂集中装配成最终产品。该模式在带来诸多好处的同时,对资源调度提出了新的挑战。针对分布式装配置换流水车间调度问题(distributed assembly permutation flowshop scheduling problem,DAPFSP),介绍了DAPFSP的背景和存在的主要困难,进而对以最小化最大完工时间为优化目标的DAPFSP,从数学模型、编解码策略、全局和局部搜索算法角度进行探讨,分别综述了以最小化总流程时间等为优化目标,具有零等待等约束,以及考虑准备时间等因素的DAPFSP研究成果。最后,对有待进一步开展的研究工作进行展望。

基于内分泌激素调节机制的免疫算法的Flowshop调度问题

针对不确定条件下具有零等待的Flowshop调度问题,采用三角模糊数来描述不确定的产品处理时间,在模糊规划理论的基础上建立了相应的调度模型,通过中间值最大隶属度算法,将原来的模糊调度模型转化为单目标的规划模型;并基于内分泌激素调节规律,利用内分泌系统与免疫系统之间密切的双向调节关系,提出了一种新颖的解决此类问题的自适应内分泌免疫调度算法。仿真实例表明,该算法的收敛速度和搜索精度均明显优于改进的免疫算法,表明该算法的有效性和优越性。

基于遗传算法的混合Flowshop调度

混合Flowshop调度问题,是一个NP完全问题,很难用一般的方法解决,文章提出了遗传算法求解混合Flow-shop调度问题的方法,给出了一种染色体表示方法,设计了相应的交叉和变异操作算子,这两种算子很容易保证个体的合法性,同时又具有遗传算法本身所要求的随机性。最后给出了一个较大规模的计算实例,仿真结果表明此算法是有效的。

一种求解同顺序 Flowshop 排序问题的新的启发式算法

在生产调度中经常遇到工件排序问题，这类问题大多属于ＮＰ类问题．对此，目前无论在理论上还是在实际应用中，都尚未找到令人满意的一般求解方法．针对ＮＰ类问题中的一类——同顺序Ｆｌｏｗｓｈｏｐ排序问题，进行了广泛而深入的调查和比较研究，在此基础上，提出了一种新的启发式算法（简称为ＷＳＨ法），并通过大量的数据实验将该算法与目前已知较好的几种算法进行了比较．结果表明，ＷＳＨ法结构简单，计算效率高，是求解中、小规模问题的较好算法．