A Neural Network Application in Personnel Scheduling

In this paper, we present and evaluate a neural network model for solving a typical personnel-scheduling problem, i.e. an airport ground staff rostering problem. Personnel scheduling problems are widely found in servicing and manufacturing industries. The inherent complexity of personnel scheduling problems has normally resulted in the development of integer programming-based models and various heuristic solution procedures. The neural network approach has been admitted as a promising alternative to solving a variety of combinatorial optimization problems. While few works relate neural network to applications of personnel scheduling problems, there is great theoretical and practical value in exploring the potential of this area. In this paper, we introduce a neural network model following a relatively new modeling approach to solve a real rostering case. We show how to convert a mixed integer programming formulation to a neural network model. We also provide the experiment results comparing the neural network method with three popular heuristics, i.e. simulated annealing, Tabu search and genetic algorithm. The computational study reveals some potential of neural networks in solving personnel scheduling problems.     

Risk optimization with p-order conic constraints: A linear programming approach

The paper considers solving of linear programming problems with p-order conic constraints that are related to a certain class of stochastic optimization models with risk objective or constraints. The proposed approach is based on construction of polyhedral approximations for p-order cones, and then invoking a Benders decomposition scheme that allows for efficient solving of the approximating problems. The conducted case study of portfolio optimization with p-order conic constraints demonstrates that the developed computational techniques compare favorably against a number of benchmark methods, including second-order conic programming methods.     

Iterative approximation of a solution of multi-valued variational-like inclusion in Banach spaces: A P-η-proximal-point mapping approach

In this paper, we introduce a class of P-η-accretive mappings, an extension of η-m-accretive mappings [C.E. Chidume, K.R. Kazmi, H. Zegeye, Iterative approximation of a solution of a general variational-like inclusion in Banach spaces, Int. J. Math. Math. Sci. 22 (2004) 1159-1168] and P-accretive mappings [Y.-P. Fang, N.-J. Huang, H-accretive operators and resolvent operator technique for solving variational inclusions in Banach spaces, Appl. Math. Lett. 17 (2004) 647-653], in real Banach spaces. We prove some properties of P-η-accretive mappings and give the notion of proximal-point mapping, termed as P-η-proximal-point mapping, associated with P-η-accretive mapping. Further, using P-η-proximal-point mapping technique, we prove the existence of solution and discuss the convergence analysis of iterative algorithm, for multi-valued variational-like inclusions in real Banach space. The theorems presented in this paper extend and improve many known results in the literature.     

On the GPGPU parallelization issues of finite element approximate inverse preconditioning

During the past decades, explicit finite element approximate inverse preconditioning methods have been extensively used for efficiently solving sparse linear systems on multiprocessor systems. The effectiveness of explicit approximate inverse preconditioning schemes relies on the use of efficient preconditioners that are close approximants to the coefficient matrix and are fast to compute in parallel. New parallel computational techniques are proposed for the parallelization of the Optimized Banded Generalized Approximate Inverse Finite Element Matrix (OBGAIFEM) algorithm, based on the concept of the “fish bone” computational approach, and for the Explicit Preconditioned Conjugate Gradient type methods on a General Purpose Graphics Processing Unit (GPGPU). The proposed parallel methods have been implemented using Compute Unified Device Architecture (CUDA) developed by NVIDIA. Finally, numerical results for the performance of the finite element explicit approximate inverse preconditioning for solving characteristic two dimensional boundary value problems on a massive multiprocessor interface on a GPU are presented. The CUDA implementation issues of the proposed methods are also discussed.     

On the GPGPU parallelization issues of finite element approximate inverse preconditioning

During the past decades, explicit finite element approximate inverse preconditioning methods have been extensively used for efficiently solving sparse linear systems on multiprocessor systems. The effectiveness of explicit approximate inverse preconditioning schemes relies on the use of efficient preconditioners that are close approximants to the coefficient matrix and are fast to compute in parallel. New parallel computational techniques are proposed for the parallelization of the Optimized Banded Generalized Approximate Inverse Finite Element Matrix (OBGAIFEM) algorithm, based on the concept of the “fish bone” computational approach, and for the Explicit Preconditioned Conjugate Gradient type methods on a General Purpose Graphics Processing Unit (GPGPU). The proposed parallel methods have been implemented using Compute Unified Device Architecture (CUDA) developed by NVIDIA. Finally, numerical results for the performance of the finite element explicit approximate inverse preconditioning for solving characteristic two dimensional boundary value problems on a massive multiprocessor interface on a GPU are presented. The CUDA implementation issues of the proposed methods are also discussed.     

A neural network approach to facility layout problems

A near-optimum parallel algorithm for solving facility layout problems is presented in this paper where the problem is NP-complete. The facility layout problem is one of the most fundamental quadratic assignment problems in Operations Research. The goal of the problem is to locate N facilities on an N-square (location) array so as to minimize the total cost. The proposed system is composed of N × N neurons based on an artificial two-dimensional maximum neural network for an N-facility layout problem. Our algorithm has given improved solutions for several benchmark problems over the best existing algorithms.     

An algorithm for minimizing flow time and maximum earliness on a single machine

This study presents an algorithm for efficient scheduling in terms of total flow time and maximum earliness. All the algorithms in the literature for solving this problem are based on heuristic procedures, and cannot necessarily generate all efficient schedules. This study shows that this problem can actually be solved in pseudo-polynomial time, and develops an algorithm for so doing. The complexity of the algorithm is O (n²p? log n). Its computational performance in solving problems of various sizes is determined.     

Improved T − ψ nodal finite element schemes for eddy current problems

The aim of this paper is to propose improved T − ψ finite element schemes for eddy current problems in the three-dimensional bounded domain with a simply-connected conductor. In order to utilize nodal finite elements in space discretization, we decompose the magnetic field into summation of a vector potential and the gradient of a scalar potential in the conductor; while in the nonconducting domain, we only deal with the gradient of the scalar potential. As distinguished from the traditional coupled scheme with both vector and scalar potentials solved in a discretizing equation system, the proposed decoupled scheme is presented to solve them in two separate equation systems, which avoids solving a saddle-point equation system like the traditional coupled scheme and leads to an important saving in computational effort. The simulation results and the data comparison of TEAM Workshop Benchmark Problem 7 between the coupled and decoupled schemes show the validity and efficiency of the decoupled one.     

A bicriteria m-machine flowshop scheduling with sequence-dependent setup times

In this study, a bicriteria m-machine flowshop scheduling with sequence-dependent setup times is considered. The objective function of the problem is minimization of the weighted sum of total completion time and makespan. Only small size problems with up to 6 machines and 18 jobs can be solved by the proposed integer programming model. Also the model is tested on an example. We also proposed three heuristic approaches for solving large jobs problems. To solve the large sizes problems up to 100 jobs and 10 machines, special heuristics methods is used. Results of computational tests show that the proposed model is effective in solving problems.     

Compact group actions on equivariant absolute neighborhood retracts and their orbit spaces

We apply equivariant joins to give a new and more transparent proof of the following result: if G is a compact Hausdorff group and X a G-ANR (respectively, a G-AR), then for every closed normal subgroup H of G, the H-orbit space X/H is a G/H-ANR (respectively, a G/H-AR). In particular, X/G is an ANR (respectively, an AR).     

A meshless method for solving three-dimensional time fractional diffusion equation with variable-order derivatives

In this study a new framework for solving three-dimensional (3D) time fractional diffusion equation with variable-order derivatives is presented. Firstly, a θ-weighted finite difference scheme with second-order accuracy is introduced to perform temporal discretization. Then a meshless generalized finite difference (GFD) scheme is employed for the solutions of remaining problems in the space domain. The proposed scheme is truly meshless and can be used to solve problems defined on an arbitrary domain in three dimensions. Preliminary numerical examples illustrate that the new method proposed here is accurate and efficient for time fractional diffusion equation in three dimensions, particularly when high accuracy is desired.     

Bin packing and multiprocessor scheduling problems with side constraint on job types

This paper deals with the bin packing problem and the multiprocessor scheduling problem both with an additional constraint specifying the maximum number of jobs in each type to the processed on a processor. Since these problems are NP-complete, various approximation algorithms are proposed by generalizing those algorithms known for the ordinary bin packing and multiprocessor scheduling problems. The worst-case performance of the proposed algorithms are analyzed, and some computational results are reported to indicate their average case behavior.     

Fast directional algorithms for the Helmholtz kernel

This paper presents a new directional multilevel algorithm for solving N-body or N-point problems with highly oscillatory kernels. We address the problem by first proving that the interaction between a ball of radius r and a well-separated region has an approximate low rank representation, as long as the well-separated region belongs to a cone with a spanning angle of O(1/r) and is at a distance which is at least O(r²) away from the ball. Based on this representation, our algorithm organizes the high frequency computation using a multidirectional and multiscale strategy. Our algorithm is proved to have an optimal O(NlogN) computational complexity for any given accuracy when the points are sampled from a two-dimensional surface.     

Shop scheduling problems with multiprocessor tasks on dedicated processors

The computational complexity of shop scheduling problems with multiprocessor tasks on dedicated processors is investigated. The objective is makespan minimization. Preemption of tasks is not allowed. For open and flow-shop problems with three stages, complete classifications into polynomial solvable and NP-hard problems are given. These classifications depend on the compatibility structures of the problems. Furthermore, results for open-shop problems with unit processing times are derived. Finally, it is shown that most of the special cases of the job-shop problem which are polynomially solvable remain polynomially solvable in the multiprocessor task situation.Supported by the Deutsche Forschungsgemeinschaft, Project JoPTAG.     

Polynomial time approximation schemes and parameterized complexity

In this paper, we study the relationship between the approximability and the parameterized complexity of NP optimization problems. We introduce a notion of polynomial fixed-parameter tractability and prove that, under a very general constraint, an NP optimization problem has a fully polynomial time approximation scheme if and only if the problem is polynomial fixed-parameter tractable. By enforcing a constraint of planarity on the W-hierarchy studied in parameterized complexity theory, we obtain a class of NP optimization problems, the planar W-hierarchy, and prove that all problems in this class have efficient polynomial time approximation schemes (EPTAS). The planar W-hierarchy seems to contain most of the known EPTAS problems, and is significantly different from the class introduced by Khanna and Motwani in their efforts in characterizing optimization problems with polynomial time approximation schemes.     

Mathematical programming approaches for generating p-efficient points

Probabilistically constrained problems, in which the random variables are finitely distributed, are non-convex in general and hard to solve. The p-efficiency concept has been widely used to develop efficient methods to solve such problems. Those methods require the generation of p-efficient points (pLEPs) and use an enumeration scheme to identify pLEPs. In this paper, we consider a random vector characterized by a finite set of scenarios and generate pLEPs by solving a mixed-integer programming (MIP) problem. We solve this computationally challenging MIP problem with a new mathematical programming framework. It involves solving a series of increasingly tighter outer approximations and employs, as algorithmic techniques, a bundle preprocessing method, strengthening valid inequalities, and a fixing strategy. The method is exact (resp., heuristic) and ensures the generation of pLEPs (resp., quasi pLEPs) if the fixing strategy is not (resp., is) employed, and it can be used to generate multiple pLEPs. To the best of our knowledge, generating a set of pLEPs using an optimization-based approach and developing effective methods for the application of the p-efficiency concept to the random variables described by a finite set of scenarios are novel. We present extensive numerical results that highlight the computational efficiency and effectiveness of the overall framework and of each of the specific algorithmic techniques.     

An adaptive multiphase approach for large unconditional and conditional p-median problems

A multiphase approach that incorporates demand points aggregation, Variable Neighbourhood Search (VNS) and an exact method is proposed for the solution of large-scale unconditional and conditional p-median problems. The method consists of four phases. In the first phase several aggregated problems are solved with a “Local Search with Shaking” procedure to generate promising facility sites which are then used to solve a reduced problem in Phase 2 using VNS or an exact method. The new solution is then fed into an iterative learning process which tackles the aggregated problem (Phase 3). Phase 4 is a post optimisation phase applied to the original (disaggregated) problem. For the p-median problem, the method is tested on three types of datasets which consist of up to 89,600 demand points. The first two datasets are the BIRCH and the TSP datasets whereas the third is our newly geometrically constructed dataset that has guaranteed optimal solutions. The computational experiments show that the proposed approach produces very competitive results. The proposed approach is also adapted to cater for the conditional p-median problem with interesting results.     

Complexity of single machine scheduling problems under scenario-based uncertainty

We present algorithmic and computational complexity results for several single machine scheduling problems where some job characteristics are uncertain. This uncertainty is modeled through a finite set of well-defined scenarios. We use here the so-called absolute robustness criterion to select among feasible solutions.     

A self-adaptive global best harmony search algorithm for continuous optimization problems

This paper presents a self-adaptive global best harmony search (SGHS) algorithm for solving continuous optimization problems. In the proposed SGHS algorithm, a new improvisation scheme is developed so that the good information captured in the current global best solution can be well utilized to generate new harmonies. The harmony memory consideration rate (HMCR) and pitch adjustment rate (PAR) are dynamically adapted by the learning mechanisms proposed. The distance bandwidth (BW) is dynamically adjusted to favor exploration in the early stages and exploitation during the final stages of the search process. Extensive computational simulations and comparisons are carried out by employing a set of 16 benchmark problems from literature. The computational results show that the proposed SGHS algorithm is more effective in finding better solutions than the state-of-the-art harmony search (HS) variants.     

Resolvent operator technique for generalized implicit variational-like inclusion in Banach space

A new class of g-η-accretive mappings is introduced and studied in Banach space. By using the properties of g-η-accretive mappings, the concept of resolvent operators associated with the classical m-accretive operators is extended. And an iterative algorithm for a new class of generalized implicit variational-like inclusion involving g-η-accretive mappings and its convergence results are established in Banach space.