Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times

In this paper, we discuss a scheduling problem for jobs on identical parallel machines. Ready times of the jobs, precedence constraints, and sequence-dependent setup times are considered. We are interested in minimizing the performance measure total weighted tardiness that is important for achieving good on-time delivery performance. Scheduling problems of this type appear as subproblems in decomposition approaches for large scale job shops with automated transport of the jobs as, for example, in semiconductor manufacturing. We suggest several variants of variable neighborhood search (VNS) schemes for this scheduling problem and compare their performance with the performance of a list based scheduling approach based on the Apparent Tardiness Cost with Setups and Ready Times (ATCSR) dispatching rule. Based on extensive computational experiments with randomly generated test instances we are able to show that the VNS approach clearly outperforms heuristics based on the ATCSR dispatching rule in many situations with respect to solution quality. When using the schedule obtained by ATCSR as an initial solution for VNS, then the entire scheme is also fast and can be used as a subproblem solution procedure for complex job shop decomposition approaches.     

A two-stage stochastic programming model for the parallel machine scheduling problem with machine capacity

This paper proposes a two-stage stochastic programming model for the parallel machine scheduling problem where the objective is to determine the machines' capacities that maximize the expected net profit of on-time jobs when the due dates are uncertain. The stochastic model decomposes the problem into two stages: The first (FS) determines the optimal capacities of the machines whereas the second (SS) computes an estimate of the expected profit of the on-time jobs for given machines' capacities. For a given sample of due dates, SS reduces to the deterministic parallel weighted number of on-time jobs problem which can be solved using the efficient branch and bound of M’Hallah and Bulfin [16]. FS is tackled using a sample average approximation (SAA) sampling approach which iteratively solves the problem for a number of random samples of due dates. SAA converges to the optimum in the expected sense as the sample size increases. In this implementation, SAA applies a ranking and selection procedure to obtain a good estimate of the expected profit with a reduced number of random samples. Extensive computational experiments show the efficacy of the stochastic model.     

Size-reduction heuristics for the unrelated parallel machines scheduling problem

In this paper we study the unrelated parallel machines problem where n independent jobs must be assigned to one out of m parallel machines and the processing time of each job differs from machine to machine. We deal with the objective of the minimisation of the maximum completion time of the jobs, usually referred to as makespan or C_max. This is a type of assignment problem that has been frequently studied in the scientific literature due to its many potential applications. We propose a set of metaheuristics based on a size-reduction of the original assignment problem that produce solutions of very good quality in a short amount of time. The underlying idea is to consider only a few of the best possible machine assignments for the jobs and not all of them. The results are simple, yet powerful methods. We test the proposed algorithms with a large benchmark of instances and compare them with current state-of-the-art methods. In most cases, the proposed size-reduction algorithms produce results that are statistically proven to be better by a significant margin.     

On optimization of finite-difference time-domain (FDTD) computation on heterogeneous and GPU clusters

A model for the computational cost of the finite-difference time-domain (FDTD) method irrespective of implementation details or the application domain is given. The model is used to formalize the problem of optimal distribution of computational load to an arbitrary set of resources across a heterogeneous cluster. We show that the problem can be formulated as a minimax optimization problem and derive analytic lower bounds for the computational cost. The work provides insight into optimal design of FDTD parallel software. Our formulation of the load distribution problem takes simultaneously into account the computational and communication costs. We demonstrate that significant performance gains, as much as 75%, can be achieved by proper load distribution.     

FPGA implementation and performance evaluation of a high throughput crypto coprocessor

This paper describes the FPGA implementation of FastCrypto, which extends a general-purpose processor with a crypto coprocessor for encrypting/decrypting data. Moreover, it studies the trade-offs between FastCrypto performance and design parameters, including the number of stages per round, the number of parallel Advance Encryption Standard (AES) pipelines, and the size of the queues. Besides, it shows the effect of memory latency on the FastCrypto performance. FastCrypto is implemented with VHDL programming language on Xilinx Virtex V FPGA. A throughput of 222 Gb/s at 444 MHz can be achieved on four parallel AES pipelines. To reduce the power consumption, the frequency of four parallel AES pipelines is reduced to 100 MHz while the other components are running at 400 MHz. In this case, our results show a FastCrypto performance of 61.725 bits per clock cycle (b/cc) when 128-bit single-port L2 cache memory is used. However, increasing the memory bus width to 256-bit or using 128-bit dual-port memory, improves the performance to 112.5 b/cc (45 Gb/s at 400 MHz), which represents 88% of the ideal performance (128 b/cc).     

Support vector regression based modeling of pier scour using field data

This paper investigates the potential of support vector machines based regression approach to model the local scour around bridge piers using field data. A dataset of consisting of 232 pier scour measurements taken from BSDMS were used for this analysis. Results obtained by using radial basis function and polynomial kernel based Support vector regression were compared with four empirical relation as well as with a backpropagation neural network and generalized regression neural network. A total of 154 data were used for training different algorithms whereas remaining 78 data were used to test the created model. A coefficient of determination value of 0.897 (root mean square error=0.356) was achieved by radial basis kernel based support vector regression in comparison to 0.880 and 0.835 (root mean square error=0.388 and 0.438) by backpropagation neural and generalized regression neural network. Comparisons of results with four predictive equations suggest an improved performance by support vector regression. Results with dimensionless data using all three algorithms suggest a better performance by dimensional data with this dataset. Sensitivity analysis suggests the importance of depth of flow and pier width in predicting the scour depth when using support vector regression based modeling approach.     

支持向量机的进化多核设计

为提高支持向量机分类精度,提出一种基于遗传程序设计的进化多核算法.算法中每个个体表示一个多核函数,并采用树形结构进行编码,增强了多核函数的非线性;初始种群由生长法产生,经过遗传操作后得到适合具体问题的进化多核函数.遗传程序设计的全局搜索性能使得算法设计不需要先验知识.与单核函数及其他多核函数的对比实验结果表明,进化多核...     

Makespan minimization for two parallel machines scheduling with a periodic availability constraint

A two parallel machines scheduling problem where one machine is periodically unavailable with the objective of minimizing makespan is considered. It is showed that the worst-case ratio of the classical LPT algorithm and the competitive ratio of the LS algorithm are 3/2 and 2, respectively, for the offline version and the online version of the problem.     

Bottleneck-based heuristics to minimize total tardiness for the flexible flow line with unrelated parallel machines

This paper considers the flexible flow line problem with unrelated parallel machines at each stage and with a bottleneck stage on the line. The objective of the problem is to minimize the total tardiness. Two bottleneck-based heuristics with three machine selection rules are proposed to solve the problem. The heuristics first develop an indicator to identify a bottleneck stage in the flow line, and then separate the flow line into the upstream stages, the bottleneck stage, and the downstream stages. The upstream stages are the stages ahead of the bottleneck stage and the downstream stages are the stages behind the bottleneck stage. A new approach is developed to find the arrival times of the jobs at the bottleneck stage. Using the new approach, the bottleneck-based heuristics develop two decision rules to iteratively schedule the jobs at the bottleneck stage, the upstream stages, and the downstream stages. In order to evaluate the performance of the bottleneck-based heuristics, seven commonly used dispatching rules and a basic tabu search algorithm are investigated for comparison purposes. Seven experimental factors are used to design 128 production scenarios, and ten test problems are generated for each scenario. Computational results show that the bottleneck-based heuristics significantly outperform all the dispatching rules for the test problems. Although the effective performance of the bottleneck-based heuristics is inferior to the basic tabu search algorithm, the bottleneck-based heuristics are much more efficient than the tabu search algorithm. Also, a test of the effect of the experimental factors on the dispatching rules, the bottleneck-based heuristics, and the basic tabu search algorithm is performed, and some interesting insights are discovered.     

Fast problem-size-independent parallel prefix circuits

A family of parallel algorithms solving the prefix problem on the combinational circuit model is presented. These prefix circuits are waist-size optimal with waist 1 (WSO-1). They are not only building blocks for constructing fast depth-size optimal prefix circuits, but also themselves fast problem-size-independent prefix circuits. When the problem size is greater than the circuit width, the presented prefix circuits may very much faster than any other prefix circuits of the same width, especially when the problem size is greater than or equal to twice the circuit width. The new prefix circuits are compared analytically with other representative prefix circuits to show how fast they are. They have the minimum depth and are the fastest among all WSO-1 prefix circuits of the same width and fan-out. Thus, they are better building blocks than other WSO-1 circuits for constructing fast depth-size optimal prefix circuits with the same fan-out.