一种统一的资源预留策略

资源预留可以保证任务在开始执行时获得资源,而这在网格这样资源动态性很强的环境中是很可贵的,因而资源预留是网格任务调度中一种普遍采用的策略。当前资源预留的研究主要集中在计算资源预留的情况,文中提出了一个网格环境中资源预留的统一策略,该策略对其它资源的预留和计算资源的预留一起加以考虑,经过模拟验证,该策略能够很好地和我们先前设计的一种基于资源预留的任务映射算法结合起来,适用于网格的动态、异构性环境。     

A branch and bound algorithm for scheduling problem of a robot‐centered manufacturing cell

Abstract

An alternative formulation of the scheduling problem in a robot‐centered manufacturing cell has been described here, which was originally formulated by Lin et al. [7] as a mixed integer programming problem. An efficient procedure based on the branch and bound technique has been proposed. In order to reduce the complexity of the branching procedure, several sequencing rules [4] have been imbedded into the proposed procedure and an integrated algorithm has then been presented. The computational results have indicated the proposed algorithm to be efficient. Finally, conclusions and some suggestions are given.     

Block spatial scheduling modelling and application in shipbuilding

With the wide application of module-shipbuilding technology, problems related to block spatial scheduling occur in various working areas, and this restricts the productivity of shipbuilding. To address the problems and to obtain the optimum block sequence and spatial layout, typical block features and work plates were investigated. A heuristic spatial scheduling model was established based on the investigation and proposed strategies with the objective to minimise makespan. With the heuristic algorithm, a block spatial scheduling system was developed and implemented with real data from a large ship. Through the spatial scheduling system, visual results of daily block layouts and progress charts for all blocks can be easily obtained and work orders can also be created for site workers. Several other spatial scheduling methods are described and compared with the above-mentioned heuristic algorithm. The result shows that the heuristic algorithm is better than Cplex and a genetic algorithm in solving large-scale block scheduling, and the heuristic algorithm is better than a grid algorithm and manual scheduling in all aspects such as makespan, utilisation of work plates, runtime of scheduling and on-time delivery. The developed block spatial scheduling system is applied in a block production shop of a modern shipyard and shows good performance.     

RMRL: improved regret minimisation techniques using learning automata

Game theory as one of the most progressive areas in AI in last few years originates from the same root as AI. The unawareness of the other players and their decisions in such incomplete-information problems, make it necessary to use some learning techniques to enhance the decision-making process. Reinforcement learning techniques are studied in this research; regret minimisation (RM) and utility maximisation (UM) techniques as reinforcement learning approaches are widely applied to such scenarios to achieve optimum solutions. In spite of UM, RM techniques enable agents to overcome the shortage of information and enhance the performance of their choices based on regrets, instead of utilities. The idea of merging these two techniques are motivated by iteratively applying UM functions to RM techniques. The main contributions are as follows; first, proposing some novel updating methods based on UM of reinforcement learning approaches for RM; the proposed methods refine RM to accelerate the regret reduction, second, devising different procedures, all relying on RM techniques, in a multi-state predator-prey problem. Third, how the approach, called RMRL, enhances different RM techniques in this problem is studied. Estimated results support the validity of RMRL approach comparing with some UM and RM techniques.     

Minimising work overload in mixed-model assembly lines with different types of operators: a case study from the truck industry

This paper considers the problem of sequencing mixed-model assembly lines (MMALs). Our goal is to determine the sequence of products to minimise work overload. This problem is known as the MMAL sequencing problem with work overload minimisation: we explicitly use task operation times to find the product sequence. This paper is based on an industrial case study of a truck assembly line. In this industrial context, as a reaction to work overloads, operators at the workstations finish their tasks before the product reaches the next workstation, but at the expense of fatigue. Furthermore, there are different types of operators, each with different task responsibilities. The originality of this work is to model this new way of reacting against work overloads, to integrate three operator types in the sequencing model and to apply the developed methods in a real industrial context. To solve this problem, we propose three meta-heuristic procedures: genetic algorithm, simulated annealing and a combination of these two meta-heuristics. All the methods proposed are tested on industrial data and compared to the solutions obtained using a mixed-integer linear programme. The results show that the proposed methods considerably improve the results of the current procedure used in the case study.     

Improving the migrating birds optimization metaheuristic for the permutation flow shop with sequence-dependent set-up times

This paper addresses the problem of scheduling a set of independent jobs with set-up times on a set of machines in a permutation flow shop environment. A metaheuristic known as the Migrating Birds Optimization (MBO) is adapted for the minimization of the makespan. Two versions of the algorithm are presented. The first is a basic MBO and the second introduces additional features. An extensive computational study is conducted to analyse the efficiency of the two methods on a benchmark of instances that can be found in Sistemas de Optimizacion Aplicada (http://soa.iti.es/problem-instances). The second version outperforms by far the first one. Moreover, the results that are produced by the latter show that it is suitable for solving real-world scheduling problems.     

A branch and bound algorithm for scheduling unit size jobs on parallel batching machines to minimize makespan

In this paper, we present a branch and bound algorithm for the parallel batch scheduling of jobs having different processing times, release dates and unit sizes. There are identical machines with a fixed capacity and the number of jobs in a batch cannot exceed the machine capacity. All batched jobs are processed together and the processing time of a batch is given by the greatest processing time of jobs in that batch. We compare our method to a mixed integer program as well as a method from the literature that is capable of optimally solving instances with a single machine. Computational experiments show that our method is much more efficient than the other two methods in terms of solution time for finding the optimal solution.     

Minimizing makespan in a no-wait flowshop with two batch processing machines using estimation of distribution algorithm

This paper studies the problem of minimising makespan in a no-wait flowshop with two batch processing machines (comprised of a parallel batch processing machine and a serial batch processing machine), non-identical job sizes and unequal ready times. We propose a population-based evolutionary method named estimation of distribution algorithm (EDA). Firstly, the individuals in the population are coded into job sequences. Then, a probabilistic model is built to generate new population and an incremental learning method is developed to update the probabilistic model. Thirdly, the best-fit heuristic is used to group jobs into batches and a least idle/waiting time approach is proposed to sequence the batches on batch processing machines. In addition, some problem-dependent local search heuristics are incorporated into the EDA to further improve the searching quality. Computational simulation and comparisons with some existing algorithms demonstrate the effectiveness and robustness of the proposed algorithm. Furthermore, the effectiveness of embedding the local search method in the EDA is also evaluated.     

Five-axis machining of STL surfaces by adaptive curvilinear toolpaths

We propose a new framework for toolpath generation for five-axis machining of part surfaces represented by the StereoLithography (STL) format. The framework is based on flattening the STL part and generation of adaptive curvilinear toolpaths. The corresponding cost functions, designed to represent the accuracy and the efficiency of the toolpath, are scalar functions, such as the curvature, kinematic error, rotation angles, machining strip or material removal rate or a vector field when the tool moves along a curvilinear path partly or even entirely aligned with directions considered to be optimal. The adaptive toolpath exploits grid generation methods and biased space-filling curves, combined with adaptation to the boundary and the domain decomposition. The proposed methodology of the adaptive curvilinear toolpath (ACT) has been tested on a variety of STL surfaces, including a case study of STL dental parts. Machining crowns/implants for four basic types of human teeth, molar, premolar, canine and incisor, has been considered and analysed. The reference methods are the standard iso-parametric path, MasterCam toolpath, and advanced methods of NX9 (former UG). The experiments show that there is no universal sequence of steps applicable to every surface. However, a correct choice of the tools available within the proposed ACT-framework always leads to a substantial improvement of the toolpath, in terms of its length and the machining time.     

Robust scheduling of a two-stage hybrid flow shop with uncertain interval processing times

This paper studies the makespan minimisation scheduling problem in a two-stage hybrid flow shop. The first stage has one machine and the second stage has m identical parallel machines. Neither the processing time nor probability distribution of the processing time of each job is uncertain. We propose a robust (min–max regret) scheduling model. To solve the robust scheduling problem, which is NP-hard, we first derive some properties of the worst-case scenario for a given schedule. We then propose both exact and heuristic algorithms to solve this problem. In addition, computational experiments are conducted to evaluate the performance of the proposed algorithms.