A taxonomy for the flexible job shop scheduling problem

This chapter aims at developing a taxonomic framework to classify the studies on the flexible job shop scheduling problem (FJSP). The FJSP is a generalization of the classical job shop scheduling problem (JSP), which is one of the oldest NP-hard problems. Although various solution methodologies have been developed to obtain good solutions in reasonable time for FSJPs with different objective functions and constraints, no study which systematically reviews the FJSP literature has been encountered. In the proposed taxonomy, the type of study, type of problem, objective, methodology, data characteristics, and benchmarking are the main categories. In order to verify the proposed taxonomy, a variety of papers from the literature are classified. Using this classification, several inferences are drawn and gaps in the FJSP literature are specified. With the proposed taxonomy, the aim is to develop a framework for a broad view of the FJSP literature and construct a basis for future studies.

Parallel improved Schnorr-Euchner enumeration SE++ for the CVP and SVP

The Closest Vector Problem (CVP) and the Shortest Vector Problem (SVP) are prime problems in lattice-based cryptanalysis, since they underpin the security of many lattice-based cryptosystems. Despite the importance of these problems, there are only a few CVP-solvers publicly available, and their scalability was never studied. This paper presents a scalable implementation of an enumeration-based CVP-solver for multi-cores, which can be easily adapted to solve the SVP. In particular, it achieves super-linear speedups in some instances on up to 8 cores and almost linear speedups on 16 cores when solving the CVP on a 50-dimensional lattice. Our results show that enumeration-based CVP-solvers can be parallelized as effectively as enumeration-based solvers for the SVP, based on a comparison with a state of the art SVP-solver. In addition, we show that we can optimize the SVP variant of our solver in such a way that it becomes 35%-60% faster than the fastest enumeration-based SVP-solver to date.

Concurrency detection on finish-to-start activity precedence networks

We explore the finish-to-start precedence relations of project activities used in scheduling problems. From these relations, we devise a method to identify groups of activities that could execute concurrently, i.e. activities in the same group can all execute in parallel. The method derives a new set of relations to describe the concurrency. Then, it is represented by an undirected graph and the maximal cliques problem identifies the groups. We provide a running example with a project from our previous studies in resource constrained project cost minimization together with an example application on the concurrency detection method: the evaluation of the resource stress.

Project scheduling and cost minimization with multiple availability constrained resources under stochastic conditions

The authors propose a mathematical model to minimize the project total cost where there are multiple resources constrained by maximum availability. They assume the resources as renewable and the activities can use any subset of resources requiring any quantity from a limited real interval. The stochastic nature is inferred by means of a stochastic work content defined per resource within an activity and following a known distribution and the total cost is the sum of the resource allocation cost with the tardiness cost or earliness bonus in case the project finishes after or before the due date, respectively. The model was computationally implemented relying upon an interchange of two global optimization metaheuristics – the electromagnetism-like mechanism and the evolutionary strategies. Two experiments were conducted testing the implementation to projects with single and multiple resources, and with or without maximum availability constraints. The set of collected results shows good behavior in general and provide a tool to further assist project manager decision making in the planning phase.

An evolutionary approach to the use of Petri net based models: from parallel controllers to HW/SW co-design

"A workshop within the 19th International Conference on Applications and Theory of Petri Nets - ICATPN’1998"