Heuristics for tactical time slot management: a periodic vehicle routing problem view

In this study, we consider a tactical problem where a time slot schedule for delivery service over a given planning horizon must be selected in each zone of a geographical area. A heuristic search evaluates each schedule selection by constructing a corresponding tactical routing plan of minimum cost based on demand and service time estimates. At the end, the schedule selection leading to the best tactical routing plan is selected. The latter can then be used as a blueprint when addressing the operational problem (i.e., when real customer orders are received and operational routes are constructed). We propose two heuristics to address the tactical problem. The first heuristic is a three‐phase approach: a periodic vehicle routing problem (PVRP) is first solved, followed by a repair phase and a final improvement phase where a vehicle routing problem (VRP) with time windows is solved for each period of the planning horizon. The second heuristic tackles the problem as a whole by directly solving a PVRP with time windows. Computational results compare the two heuristics under various settings, based on instances derived from benchmark instances for the VRP with time windows.     

A memetic algorithm for the generalized traveling salesman problem

The generalized traveling salesman problem (GTSP) is an extension of the well-known traveling salesman problem. In GTSP, we are given a partition of cities into groups and we are required to find a minimum length tour that includes exactly one city from each group. The recent studies on this subject consider different variations of a memetic algorithm approach to the GTSP. The aim of this paper is to present a new memetic algorithm for GTSP with a powerful local search procedure. The experiments show that the proposed algorithm clearly outperforms all of the known heuristics with respect to both solution quality and running time. While the other memetic algorithms were designed only for the symmetric GTSP, our algorithm can solve both symmetric and asymmetric instances.     

SipaaS: Spot instance pricing as a Service framework and its implementation in OpenStack

Designing dynamic pricing mechanisms that efficiently price resources in line with a provider's profit maximization goal is a key challenge in cloud computing environments. Despite the large volume of research published on this topic, there is no publicly available software system implementing dynamic pricing for Infrastructure as a Service cloud spot markets. This paper presents the implementation of a framework called Spot instance pricing as a Service (SipaaS) that supports an auction mechanism to price and allocate virtual machine instances. SipaaS is an open‐source project offering a set of web services to price and sell virtual machine instances in a spot market resembling the Amazon EC2 spot instances. Cloud providers, who aim at utilizing SipaaS, should install add‐ons in their existing platform to make use of the framework. As an instance, we provide an extension to the Horizon – the OpenStack dashboard project – to employ SipaaS web services and to add a spot market environment to OpenStack. To validate and evaluate the system, we conducted an experimental study with a group of 10 users utilizing the provided spot market in a real environment. Results show that the system performs reliably in a practical test environment. Copyright © 2015 John Wiley & Sons, Ltd.     

Heuristics for determining a patrol path of an unmanned combat vehicle

We consider a problem of finding a path of an unmanned combat vehicle that patrols a given area by visiting a given set of checkpoints with the objective of minimizing possibility of enemy’s infiltration. In this study, we focus on a situation in which the possibility of enemy’s infiltration at (through) each checkpoint is increased nonlinearly as time passes and the checkpoint may be patrolled multiple times during a planning horizon. We develop two-phase heuristics in which an initial path is constructed in the first phase and then it is improved in the second phase. For evaluation of the performance of the proposed heuristics, computational experiments are performed on randomly generated problem instances, and results show that the heuristics give good solutions in a reasonably short time.     

Solving scalarized multi‐objective network flow problems using an interior point method

In this paper, we present a primal‐dual interior‐point algorithm to solve a class of multi‐objective network flow problems. More precisely, our algorithm is an extension of the single‐objective primal infeasible dual feasible inexact interior point method for multi‐objective linear network flow problems. Our algorithm is contrasted with standard interior point methods and experimental results on bi‐objective instances are reported. The multi‐objective instances are converted into single objective problems with the aid of an achievement function, which is particularly adequate for interactive decision‐making methods.     

Schema Matching Using Interattribute Dependencies

Schema matching is one of the key challenges in information integration. It is a labor-intensive and time-consuming process. To alleviate the problem, many automated solutions have been proposed. Most of the existing solutions mainly rely upon textual similarity of the data to be matched. However, there exist instances of the schema matching problem for which they do not even apply. Such problem instances typically arise when the column names in the schemas and the data in the columns are opaque or very difficult to interpret. In our previous work [36] we proposed a two-step technique to address this problem. In the first step, we measure the dependencies between attributes within tables using an information-theoretic measure and construct a dependency graph for each table capturing the dependencies among attributes. In the second step, we find matching node pairs across the dependency graphs by running a graph matching algorithm. In our previous work, we experimentally validated the accuracy of the approach. One remaining challenge is the computational complexity of the graph matching problem in the second step. In this paper we extend the previous work by improving the second phase of the algorithm incorporating efficient approximation algorithms into the framework.     

Exact methods and a heuristic for the optimization of an integrated replenishment-storage planning problem

In this paper we study the coordination of different activities in a supply chain issued from a real case. Multiple suppliers send raw materials (RMs) to a distribution center (DC) that delivers them to a unique plant where the storage of the RMs and the finished goods is not possible. Then, the finished goods are directly shipped to multiple customers having just‐in‐time (JIT) demands. Under these hypotheses, we show that the problem can be reduced to multiple suppliers and one DC. Afterwards, we analyze two cases; in the first, we consider an uncapacitated storage at DC, and in the second, we analyze the capacitated storage case. For the first case, we show that the problem is NP‐hard in the ordinary sense using the Knapsack decision problem. We then propose two exact methods: a mixed integer linear program (MILP) and a pseudopolynomial dynamic program. A classical dynamic program and an improved one using the idea of Shaw and Wagelmans are given. With numerical tests we show that the dynamic program gives the optimal solution in reasonable time for quite large instances compared with the MILP. For the second case, the capacity limitation in DC is assumed, which makes the problem solving more challenging. We propose an MILP and a dynamic programming‐based heuristic that provides solutions close to the optimal solution in very short times.     

Optimizing the operating conditions in a high precision industrial process using soft computing techniques

This interdisciplinary research is based on the application of unsupervized connectionist architectures in conjunction with modelling systems and on the determining of the optimal operating conditions of a new high precision industrial process known as laser milling. Laser milling is a relatively new micro‐manufacturing technique in the production of high‐value industrial components. The industrial problem is defined by a data set relayed through standard sensors situated on a laser‐milling centre, which is a machine tool for manufacturing high‐value micro‐moulds, micro‐dies and micro‐tools. The new three‐phase industrial system presented in this study is capable of identifying a model for the laser‐milling process based on low‐order models. The first two steps are based on the use of unsupervized connectionist models. The first step involves the analysis of the data sets that define each case study to identify if they are informative enough or if the experiments have to be performed again. In the second step, a feature selection phase is performed to determine the main variables to be processed in the third step. In this last step, the results of the study provide a model for a laser‐milling procedure based on low‐order models, such as black‐box, in order to approximate the optimal form of the laser‐milling process. The three‐step model has been tested with real data obtained for three different materials: aluminium, cooper and hardened steel. These three materials are used in the manufacture of micro‐moulds, micro‐coolers and micro‐dies, high‐value tools for the medical and automotive industries among others. As the model inputs are standard data provided by the laser‐milling centre, the industrial implementation of the model is immediate. Thus, this study demonstrates how a high precision industrial process can be improved using a combination of artificial intelligence and identification techniques.     

Design, engineering, and experimental analysis of a simulated annealing approach to the post-enrolment course timetabling problem

The post-enrolment course timetabling (PE-CTT) is one of the most studied timetabling problems, for which many instances and results are available. In this work we design a metaheuristic approach based on simulated annealing to solve the PE-CTT. We consider all the different variants of the problem that have been proposed in the literature and we perform a comprehensive experimental analysis on all the available public instances. The outcome is that our solver, properly engineered and tuned, performs very well on all cases, providing the new best known results on many instances and state-of-the-art values for the others.     

Position‐Based Simulation of Elastic Models on the GPU with Energy Aware Gauss‐Seidel Algorithm

In this paper, we provide a smooth extension of the energy aware Gauss‐Seidel iteration to the Position‐Based Dynamics (PBD) method. This extension is inspired by the kinetic and potential energy changes equalization and uses the foundations of the recent extended version of PBD algorithm (XPBD). The proposed method is not meant to conserve the total energy of the system and modifies each position constraint based on the equality of the kinetic and potential energy changes within the Gauss‐Seidel process of the XPBD algorithm. Our extension provides an implicit solution for relatively better stiffness during the simulation of elastic objects. We apply our solution directly within each Gauss‐Seidel iteration and it is independent of both simulation step‐size and integration methods. To demonstrate the benefits of our proposed extension with higher frame rates, we develop an efficient and practical mesh coloring algorithm for the XPBD method which provides parallel processing on a GPU. During the initialization phase, all mesh primitives are grouped according to their connectivity. Afterwards, all these groups are computed simultaneously on a GPU during the simulation phase. We demonstrate the benefits of our method with many spring potential and strain‐based continuous material constraints. Our proposed algorithm is easy to implement and seamlessly fits into the existing position‐based frameworks.     

Computing with words via Turing machines: a formal approach

Computing with words (CW) as a methodology, means computing and reasoning by the use of words in place of numbers or symbols, which may conform more to humans' perception when describing real-world problems. In this paper, as a continuation of a previous paper, we aim to develop and deepen a formal aspect of CW. According to the previous paper, the basic point of departure is that CW treats certain formal modes of computation with strings of fuzzy subsets instead of symbols as their inputs. Specifically, 1) we elaborate on CW via Turing machine (TM) models, showing the time complexity is at least exponential if the inputs are strings of words; 2) a negative result of (6) not holding is verified which indicates that the extension principle for CW via TMs needs to be re-examined; 3) we discuss CW via context- free grammars and regular grammars and the extension principles for CW via these formal grammars are set up; 4) some equivalences between fuzzy pushdown automata (respectively, fuzzy finite-state automata) fuzzy context-free grammars (respectively, fuzzy regular grammars) are demonstrated in the sense that the inputs are instead strings of words; 5) some instances are described in detail. Summarily formal aspect of CW is more systematically established more deeply dealt with while some new problems also emerge.     

A two-phase mathematical-programming heuristic for flexible assignment of activities and tasks to work shifts

In the service industry, workers perform work shifts and are assigned to interruptible activities and uninterruptible tasks during their shifts. The work shifts of regular employees are often established several weeks in advance of the operations when the activity and task demands are still uncertain. Just a few days before the operations when these demands are unveiled with more certainty, the planned schedules can be slightly modified and on-call temporary employees can be scheduled to satisfy the demands as best as possible. As acceptable modifications, extending the planned shifts and moving workers’ meal breaks are considered. In this paper, we are interested in the scheduling problem encountered in this second step, which also involves assigning activities and tasks to the scheduled work shifts. To produce good-quality solutions in fast computational times for large-sized instances, we develop a two-phase heuristic. In the first phase, an approximate mixed-integer programming model is used to suggest temporary shifts and extensions to regular shifts and to schedule and assign tasks. In the second phase, a column-generation heuristic embedded in a rolling horizon procedure determines the final shifts and assigns activities to them. Computational results obtained on randomly generated instances are reported to evaluate the validity of the proposed solution method.     

A scatter search for a multi-type transshipment point location problem with multicommodity flow

In this paper, we consider a multi-type transshipment point location problem with multicommodity flow which aims at locating transshipment points (TPs) and determining the type for each open TP. As an extension of the classical two-stage capacitated facility location problem, our problem allows flows of commodities to move among TPs and does not impose restrictions on the number of TPs traversed by flows going from plants to customers. In order to obtain high-quality feasible solutions, we propose a clustering-based scatter search in which the seed solution generation, the diversification technique and the local search are designed using the clusters generated by a data mining technique, the K-means method. The computational results show that the scatter search performs efficiently over different kinds of instances. Moreover, the solution quality is also good since the average gaps to lower bounds range between 1 and 3%.     

Hybrid flow shop scheduling with not-all-machines options via local search with controlled deterioration

In this study we consider hybrid flow shop scheduling problem with a decision referring to the number of machines to be used. A simple way is used to decide the number of the used machines. A novel local search with controlled deterioration (CDLS) is proposed, which is composed of multiple neighborhood searches with the prefixed number of iterations and deterioration step. The deterioration step tries to obtain a new current solution with the controlled deteriorated degree on the solution quality. CDLS is tested on a number of instances and the computational results show that CDLS can provide the promising results for the considered problem.     

A novel local search algorithm with configuration checking and scoring mechanism for the set k‐covering problem

The set k‐covering problem, an extension of the classical set covering problem, is an important NP‐hard combinatorial optimization problem with extensive applications, including computational biology and wireless network. The aim of this paper is to design a new local search algorithm to solve this problem. First, to overcome the cycling problem in local search, the set k‐covering configuration checking (SKCC) strategy is proposed. Second, we use the cost scheme of elements to define the scoring mechanism so that our algorithm can find different possible good‐quality solutions. Having combined the SKCC strategy with the scoring mechanism, a subset selection strategy is designed to decide which subset should be selected as a candidate solution component. After that, a novel local search framework, as we call DLL_ccsm (diversion local search based on configuration checking and scoring mechanism), is proposed. DLL_ccsm is evaluated against two state‐of‐the‐art algorithms. The experimental results show that DLL_ccsm performs better than its competitors in terms of solution quality in most classical instances.     

A performance evaluation model for FMS based on RAM and LCC using FACTOR/AIM

The objective of this study is to develop a general design and performance evaluation model for the system designers in the initial design phase of the integrated manufacturing system based on the RAM(Reliability, Availability and Maintainability) and life cycle cost(LCC). The methodology proposed in this research includes the following three-step generative approach. First, a deterministic approach to find the optimal system configuration for the initial system configuration is considered under the assumption that the system availability is one(no failure and maintenance), and in second step a stochastic simulation model based on RAM and LCC is developed. Using the results of this two-stage simulation, a system performance index(SPI) was developed for the performance evaluation of the system. In the last step we developed a simulation model using FACTOR/AIM to consider a variety of performance factors and compared the results through a sample example.     

一类非最小相位过程内模控制系统设计

非最小相位过程是较难控制的一类过程。针对一类自衡二阶非最小相位过程 ,采用内模控制系统结构 ,使系统具有良好的抗扰性和鲁棒性。给出了在希望的幅值和相角裕量下控制器参数的计算方法。设计例子与仿真结果表明 ,根据该方法设计的系统有比较理想的稳定性和鲁棒性     

The contractor time–cost–credit trade‐off problem: integer programming model,heuristic solution,and business insights

Contractors in the construction sector face several trade‐offs between time and cost. The time–cost trade‐off (TCT) is one of these trade‐offs where contractors can reduce a project completion time by assigning more resources to activities, which means spending more money, to shorten the execution times of project activities. On the other hand, contractors who finance their projects through credit lines from banks such that if they reach their credit limits, then the start times of some project activities can be delayed until cash is available again, which might lead to an increase in the project execution time; thus, contractors need to consider the time–credit trade‐off. In this work, we simultaneously consider these two trade‐offs that affect the project completion time and use mixed integer linear programming (MILP) to model the contractor time–cost–credit trade‐off (TCCT) problem. The MILP model minimizes the project execution time given the contractor's budgetary and financial constraints. In addition to the MILP model, we also develop a heuristic solution algorithm to solve the problem. Through a set of benchmark instances, we study the effectiveness of the heuristic algorithm and the computation time of the exact model. It is found that a good upper bound for the MILP results in less computation time. We also study some practical aspects of the problem where we highlight the importance of expediting contractor payments in addition to selecting a financially stable contractor. Finally, we use our MILP model to help a contractor bid for a project.     

Hybrid greedy heuristics based on linear programming for the three‐dimensional single bin‐size bin packing problem

In this paper, we propose to solve the three‐dimensional single bin‐size bin packing problem (3D‐SBSBPP) using a simple strategy based on integer linear programming (ILP) heuristics, without using any improvement based on metaheuristics. We first propose an ILP that is converted into a series of three‐dimensional single knapsack problems (3D‐SKP). Then, the first tailored heuristic can be viewed as a hybrid approach in which both “selection” and “positioning” phases are combined. The first phase serves to select a subset of items where each of these items is susceptible to belonging to an active container. The positioning phase serves to pack a subset of items already preselected by the selection phase. Then, both phases cooperate till packing all items into their corresponding containers. The second heuristic can be viewed as an extended version of the first one. Indeed, before deciding whether the current container is closed or a new container is activated, “a local reoptimization phase” is considered. Finally, both proposed heuristics are evaluated on a set of random instances obtained by using the standard generator scheme of the literature. The provided results show that both proposed heuristics remain competitive when compared to the results obtained by one of the best methods of the literature.     

An enhanced exact procedure for the absolute robust shortest path problem

The aim of this paper is to investigate the use of heuristic information to efficiently solve to optimality the robust shortest path problem. Starting from the exact algorithm proposed by Murty and Her, we describe how this algorithm can be enhanced by using heuristic rules and evaluation functions to guide the search. The efficiency of the proposed enhanced approach is tested over a range of random generated instances. Our computational results indicate that the use of heuristic criteria is able to speed up considerably the search and that the enhanced exact solution method outperforms the state‐of‐the‐art algorithm proposed by Murty and Her in most of the instances.