柔性调度多目标优化的混合粒子群算法研究

研究多目标柔性调度问题,提出了一种基于多目标粒子群优化算法和局域搜索技术相结合的新算法.建立以最大完成时间、机器总负载和最大机器负载为目标函数的多目标数学调度模型.将粒子群算法运用到机器分配子问题;局域搜索技术运用到工序排列子问题,对粒子群算法得到的结果进行再调度.粒子群优化算法的全局搜索能力与局域搜索技术相结合,加快了算法的收敛速度.最后通过与其他算法进行测试比较,验证了该算法的可行性及有效性.     

工期不确定的模具车间作业调度前置处理

模具制造属于非重复性单件订货生产,模具加工的任务工期具有较强的不确定性,交货期往往难以保证.针对这一实际问题,建立任务工期离散概率模型,通过对不同任务的工期离散点进行组合计算,并对组合结果做交互式的包络分析,筛选出具有代表性的工期组合,作为制定具有可执行性和指导性车间作业基准调度的基础.     

Job-shop问题基于RBF网络的自学习算法

通过对Job-shop问题分析,在逐步添加约束到有向图模型来获取可行调度方案基础上,提出一种具备自动学习功能智能算法.设计了可互换工序对4种选取函数,并以此作为网络输入构建了基于RBF的神经网络以实现对可互换工序对选取.利用最小均方算法对网络权重进行训练,经过对更新过的样本进行再学习后,网络选取可互换工序对的准确度得以提高,使算法具备自学习能力.数值仿真结果表明所提算法对于大规模Job-shop问题求解存在较好效果,具较好的应用价值.     

Recursive learning method for knowledge-based planning system

In the status selection planning system, which is a kind of knowledge-based planning system, the quality of the solution depends on the status selection rules. However, it is usually difficult to acquire useful knowledge from human experts. The learning method of a status selection rule using inductive learning is proposed. The status selection rules are divided into several stages according to the planning process. Gathering a training set and learning a part of the knowledge inductively are repeated one by one from the previous stage rules. From the result of application to a job-shop problem, the effectiveness of the proposed method is shown.     

The strategies and parameters of tabu search for job-shop scheduling

This paper presents a tabu search approach for the job-shop scheduling problem. Although the problem is NP-hard, satisfactory solutions have been obtained recently by tabu search. However, tabu search has a problem-specific and parametric structure. Therefore, in the paper, we focussed on the tabu search strategies and parameters such as initial solution, neighborhood structure, tabu list, aspiration criterion, elite solutions list, intensification, diversification and the number of iteration. In order to compare some neighborhood strategies and tabu list length methods, a computational study is done on the benchmark problems.     

加工工序非紧密衔接的车间调度策略

针对以往车间调度算法忽略非紧密衔接工序调度,从而导致调度结果不精确这一情况,提出了一种考虑工序间空闲时间延迟约束的调度策略,即解决加工工序非紧密衔接调度问题的方法。该方法在对由延迟约束造成的工序非紧密衔接型调度问题进行定义和研究的基础上,提出了标准工序、延迟工序和扩展加工工艺树概念。设计了一种将延迟约束转换为顺序约束的转换策略,使得转换后的非紧密衔接工序变为虚拟紧密衔接工序,并可采用经典车间调度算法调度。实例验证表明,该调度策略可有效地解决非紧密衔接工序调度问题,可在不增加算法复杂度的情况下,得到更为实用的调度方案。     

基于多层编码遗传算法的两阶段装配式建筑预制构件生产调度优化

随着装配式建筑技术的发展和应用,多种类、多数量的预制混凝土构件生产进度优化问题随之产生,并且日益成为行业市场提升生产效率和竞争力的关键因素。在对比分析预制构件生产与一般制造业区别的基础上提出预制构件厂生产参数的量化途径,采用基于多层编码遗传算法解决预制构件的生产调度优化问题;提出两阶段的优化模式从而实现优化算法准确性的提升,使得预制构件生产企业有效优化生产管理、提升资金使用效率从而实现增效降本。     

Two decompositions for the bicriteria job-shop scheduling problem with discretely controllable processing times

The job-shop scheduling problem with discretely controllable processing times (JSP-DCPT) is a combination of two kinds of sub-problems: the job-shop scheduling problem and the discrete time-cost tradeoff problem. Neither good approximation algorithms nor efficient exact algorithms exist for the bicriteria JSP-DCPT that is to simultaneously minimise the duration and the cost of performing schedules to the problem. An assignment-first decomposition (AFD) and a sequencing-first decomposition (SFD) are proposed for solving the problem. The main difference between the two decompositions lies in the logical sequence for solving the two kinds of sub-problems. The comparison is carried out by evaluating the size of the searching space with respect to each of the two decompositions, and a general conclusion is deduced that for the JSP-DCPT with at least two machines, at least two jobs, and at least two modes for each operation, the efficiency of the searching-based approaches incorporating SFD is superior to that incorporating AFD. Computational studies on JSP-DCPT instances constructed based on a set of well-known JSP benchmarks illustrate the overall superiority of SFD to AFD regarding multiple measure metrics.     

A GRASP algorithm for flexible job-shop scheduling with maintenance constraints

In most realistic situations, machines may be unavailable due to maintenance, pre-schedules and so on. The availability constraints are non-fixed in that the completion time of the maintenance task is not fixed and has to be determined during the scheduling procedure. In this paper a greedy randomised adaptive search procedure (GRASP) algorithm is presented to solve the flexible job-shop scheduling problem with non-fixed availability constraints (FJSSP-nfa). The GRASP algorithm is a metaheuristic algorithm which is characterised by multiple initialisations. Basically, it operates in the following manner: first a feasible solution is obtained, which is then further improved by a local search technique. The main objective is to repeat these two phases in an iterative manner and to preserve the best found solution. Representative FJSSP-nfa benchmark problems are solved in order to test the effectiveness and efficiency of the proposed algorithm.     

基于最短处理时间疫苗的免疫遗传算法优化FJSP问题

合理的作业调度方案能提高加工机器的利用率。针对柔性作业车间调度求解难度更大的特点,采用免疫遗传算法求解。在疫苗技术方面,提出依据工件工序加工时间表,选择同工件同工序加工时间最短的机器作为疫苗,对相应工件个体机器码接种。最后对测试案例求解,结果表明所采取的方法能够求得更好的调度方案,减少机器空闲时间。