A multi-objective approach to the application of real-world production scheduling

An initiative was introduced in one of the production facilities of Germany’s E.G.O. Group in order to enhance its SAP information system with a custom-made application for production-scheduling optimization. The goal of the optimization is to find a production schedule that satisfies different, contradictory production and business constraints. We show the challenges faced in the application of the multi-objective optimization approach, which is gaining influence in the management of production scheduling. We implement a memetic version of the Indicator-Based Evolutionary Algorithm with customized reproduction operators and local search procedures to find a set of feasible, non-dominated solutions. Such a memetic algorithm was applied to two real order lists from the production company. Additionally, we also lay out an efficient presentation of the multi-objective results for an expert’s support in decision making. This provides the management with the possibility to gain additional insights into how the production schedule dynamically reacts to changes in the decision criteria. We show that the multi-objective approach is able to find high-quality solutions, which enables flexibility when it comes to quickly adapting to specific business conditions.     

超立方体网络中任务调度的一个新近似算法

本文研究超立方体中的多处理器任务调度问题,我们研究LDLPT算法并指出为什么这种算法对一些实例具有最差的逼近度,然后提出一种类似装箱算法的新算法-BPA算法,证明该算法和LDLPT算法在相互最差逼近度中具有互补性质,最后,组合这两种算法的基本方法提出了一种求解问题的新算法-CBPA算法,并证明新算法具有比LDLPT算法更好的逼近度。     

Statistical Analysis and Modeling of Jobs in a Grid Environment

The existence of good probabilistic models for the job arrival process and the delay components introduced at different stages of job processing in a Grid environment is important for the improved understanding of the Grid computing concept. In this study, we present a thorough analysis of the job arrival process in the EGEE infrastructure and of the time durations a job spends at different states in the EGEE environment. We define four delay components of the total job delay and model each component separately. We observe that the job inter-arrival times at the Grid level can be adequately modelled by a rounded exponential distribution, while the total job delay (from the time it is generated until the time it completes execution) is dominated by the computing element’s register and queuing times and the worker node’s execution times. Further, we evaluate the efficiency of the EGEE environment by comparing the job total delay performance with that of a hypothetical ideal super-cluster and conclude that we would obtain similar performance if we submitted the same workload to a super-cluster of size equal to 34% of the total average number of CPUs participating in the EGEE infrastructure. We also analyze the job inter-arrival times, the CE’s queuing times, the WN’s execution times, and the data sizes exchanged at the kallisto.hellasgrid.gr cluster, which is node in the EGEE infrastructure. In contrast to the Grid level, we find that at the cluster level the job arrival process exhibits self-similarity/long-range dependence. Finally, we propose simple and intuitive models for the job arrival process and the execution times at the cluster level.     

基于ILOG平台的求解动态车间作业调度问题优化算法研究

研究了基于约束规划和启发式搜索算法结合求解动态车间作业调度的问题。以最小化制造周期费用与总拖期惩罚费用之和为优化目标,通过建立调度模型、分析问题的优化特性,提出了基于约束规划的禁忌搜索启发式算法,根据与另外两种算法的比较结果,验证了此算法的有效性。     

求解Job Shop调度问题的自适应遗传算法设计

针对标准遗传算法中交叉概率Pc和变异概率Pm固定不变带来的局限性,以及M.Sr-invivas自适应遗传算法的缺点,提出了根据适应值集中程度,自适应地变化整个种群的Pc和Pm的一种改进的自适应遗传算法,文中系统地介绍了算法的改进及算法的流程,并将算法应用于求解JSP问题,最后用一个典型的测试例子,对本文设计的算法的求解效果进行了测试,并对测试结果进行了分析.     

An integrated job release and scheduling approach on parallel machines: An application in electric wire-harness industry

This paper presents a new job release (JR) and scheduling methodology for one-stage parallel machines where sequence dependent setup times exist. A decision support system (DSS) based on job release is developed in order to enable the application of the methodology. First, mathematical programming models for both job release and job scheduling are devised. Then, due to the NP-hard nature of the problems, heuristics are proposed. As for the interaction between JR and scheduling, job scheduling is integrated with job release for the proposed heuristic solutions so that the capacity achievement provided by scheduling can be utilized for job release. In brief, product design characteristics oriented scheduling affects JR in the proposed approach. Moreover, value stream mapping (VSM) approach is used with the aim of stating the effect of the proposed methodology. Furthermore, the presented methodology was applied in a real life electric wire-harness production system. The application, based on 120-day production data, revealed that the proposed methodology provided 25% decrease in in-plant manufacturing lead time.     

多工艺路线的批量生产调度优化

以优化生产周期为目标,研究了多工艺路线的批量调度问题,提出了一种基于工序优先级的调度算法,并将该算法嵌入到遗传算法中,得到了全局优化的批量调度算法。遗传算法搜索最佳染色体,调度算法把染色体解码为调度。在调度算法中,采用了3种提高生产率的策略,即区分批量启动时间与工序加工时间,在工件到达机床之前做好准备工作;把一批工件分成多个小生产批次,每批次独立加工:一批工件加工部分后就运向后续加工机床,缩小后续机床的等待时间。仿真表明,该调度方法能取得较好结果。     

一种动态识别瓶颈机床的启发算法

瓶颈机床是影响车间生产和调度的关键因素。针对Jobshop调度中的瓶颈机床确定问题,提出了动态识别瓶颈机床的搜索算法框架。并详细讨论了算法框架中的工序开始时间窗、搜索空间的概率模型和动态启发算法。最后用算例验证了动态启发算法的有效性。     

Mathematical modelling of multi-objective job shop scheduling with dependent setups and re-entrant operations

For the last thirty years, in job shop scheduling, the setup times of operations have been either ignored or combined with their corresponding processing times, independent setups, to simplify the work of model construction. However, in practice, the setup times of an operation are usually considered be sequence-dependent. Moreover, the performance of a scheduling system is not evaluated to satisfy a single objective, but to obtain a trade-off solution regarding multiple objectives. Therefore, this paper investigates job shop scheduling problems with re-entrant operations where the setup times, which vary according to the preceding operation which is processed on the same machine, and which can be separated from their corresponding processing times, cannot be omitted. Three practical performance measures – minimum total job flow time, minimum total job tardiness and minimum machine idle time – are considered. An integer programming model is first developed to optimise each single objective and an acceptable trade-off schedule, which makes use of a multiple-decision-making technique, the global criterion method, is obtained by evaluating three objectives simultaneously .     

一种基于模拟退火算法的作业车间调度算法

通过对传统模拟退火算法(SA)和移动瓶颈法(SB)各自算法流程的分析,提出了一种改进的模拟退火算法。算法以模拟退火算法为主体流程,在主体流程过程中融入改进的移动瓶颈技术,在满足接受概率下,优化待接受的解,加快算法的收敛速度。通过对JSP优化问题的仿真试验,改进后的模拟退火算法对大规模组合优化问题求解效率有很大提高。