•A scatter search algorithm for mixed blocking permutation flowshop scheduling.•A new and effective NEH-based heuristic is used in initial solution generation.•A greedy job selection within insert ...and swap operators are used in local search.•Outperforms state-of-the-art algorithms on well-known benchmark problem sets.
Empty or limited storage capacities between machines introduce various types of blocking constraint in the industries with flowshop environment. While large applications demand flowshop scheduling with a mix of different types of blocking, research in this area mainly focuses on using only one kind of blocking in a given problem instance. In this paper, using makespan as a criterion, we study permutation flowshops with zero capacity buffers operating under mixed blocking conditions. We present a very effective scatter search (SS) algorithm for this. At the initialisation phase of SS, we use a modified version of the well-known Nawaz, Enscore and Ham (NEH) heuristic. For the improvement method in SS, we use an Iterated Local Search (ILS) algorithm that adopts a greedy job selection and a powerful NEH-based perturbation procedure. Moreover, in the reference set update phase of SS, with small probabilities, we accept worse solutions so as to increase the search diversity. On standard benchmark problems of varying sizes, our algorithm very significantly outperforms well-known existing algorithms in terms of both the solution quality and the computing time. Moreover, our algorithm has found new upper bounds for 314 out of 360 benchmark problem instances.
Protein backbone angle prediction has achieved significant accuracy improvement with the development of deep learning methods. Usually the same deep learning model is used in making prediction for ...all residues regardless of the categories of secondary structures they belong to. In this paper, we propose to train separate deep learning models for each category of secondary structures. Machine learning methods strive to achieve generality over the training examples and consequently loose accuracy. In this work, we explicitly exploit classification knowledge to restrict generalisation within the specific class of training examples. This is to compensate the loss of generalisation by exploiting specialisation knowledge in an informed way.
The new method named SAP4SS obtains mean absolute error (MAE) values of 15.59, 18.87, 6.03, and 21.71 respectively for four types of backbone angles Formula: see text, Formula: see text, Formula: see text, and Formula: see text. Consequently, SAP4SS significantly outperforms existing state-of-the-art methods SAP, OPUS-TASS, and SPOT-1D: the differences in MAE for all four types of angles are from 1.5 to 4.1% compared to the best known results.
SAP4SS along with its data is available from https://gitlab.com/mahnewton/sap4ss .
•Studying the prize-collecting arc routing problems (PARPs) with real-time scenarios.•Proposing constructive heuristics and metaheuristic algorithm to solve the problem.•Outperforming the ...best-existing methods in the literature.
Time-dependent prize-collecting arc routing problems (TD-PARPs) generalise the regular prize-collecting arc routing problems (PARPs). PARPs have arcs associated with collectable prizes along with travelling costs. TD-PARPs allow travel times to vary at the travelling horizon so that real-life uncertain factors such as traffic and weather conditions can be taken into account. A TD-PARP is to find a travelling route that maximises the profit i.e. total collected prizes minus total travelling costs. TD-PARPs have two facets: selecting a subset of arcs to be travelled and scheduling the selected arcs in the travelling route. TD-PARPs have not been studied much although they are more realistic and generic. In this paper, we first propose a set of deterministic heuristic search algorithms that range from a simple procedure producing quite good results in a fraction of a CPU second to a more extensive procedure producing high-quality results but at the expense of slightly extra CPU time. In this paper, we then propose a meta-heuristic based scatter search (SS) algorithm for TD-PARPs. For the improvement method in the SS algorithm, we propose a multi-operator algorithm that incorporates various neighbourhood operators to diversify the local exploration. For the combination method in the SS algorithm, we propose a 2-level path relinking procedure, which explores combinations of visited and unvisited arcs using two different operators. To control the diversity of the solutions in the SS algorithm, we propose a new effective distance measurement. The experimental results on standard benchmark problems indicate that the proposed SS algorithm significantly outperforms the state-of-the-art existing methods.
Protein structure prediction is a grand challenge. Prediction of protein structures via the representations using backbone dihedral angles has recently achieved significant progress along with the ...on-going surge of deep neural network (DNN) research in general. However, we observe that in the protein backbone angle prediction research, there is an overall trend to employ more and more complex neural networks and then to throw more and more features to the neural networks. While more features might add more predictive power to the neural network, we argue that redundant features could rather clutter the scenario and more complex neural networks then just could counterbalance the noise. From artificial intelligence and machine learning perspectives, problem representations and solution approaches do mutually interact and thus affect performance. We also argue that comparatively simpler predictors can more easily be reconstructed than the more complex ones. With these arguments in mind, we present a deep learning method named Simpler Angle Predictor (SAP) to train simpler DNN models that enhance protein backbone angle prediction. We then empirically show that SAP can significantly outperform existing state-of-the-art methods on well-known benchmark datasets: for some types of angles, the differences are 6-8 in terms of mean absolute error (MAE). The SAP program along with its data is available from the website https://gitlab.com/mahnewton/sap .
Protein structure prediction (PSP) has achieved significant progress lately via prediction of inter-residue distances using deep learning models and exploitation of the predictions during ...conformational search. In this context, prediction of large inter-residue distances and also prediction of distances between residues separated largely in the protein sequence remain challenging. To deal with these challenges, state-of-the-art inter-residue distance prediction algorithms have used large sets of coevolutionary and non-coevolutionary features. In this paper, we argue that the more the types of features used, the more the kinds of noises introduced and then the deep learning model has to overcome the noises to improve the accuracy of the predictions. Also, multiple features capturing similar underlying characteristics might not necessarily have significantly better cumulative effect. So we scrutinise the feature space to reduce the types of features to be used, but at the same time, we strive to improve the prediction accuracy. Consequently, for inter-residue real distance prediction, in this paper, we propose a deep learning model named scrutinised distance predictor (SDP), which uses only 2 coevolutionary and 3 non-coevolutionary features. On several sets of benchmark proteins, our proposed SDP method improves mean Local Distance Different Test (LDDT) scores at least by 10% over existing state-of-the-art methods. The SDP program along with its data is available from the website https://gitlab.com/mahnewton/sdp .
•Studying mixed blocking flowshop scheduling problems with sequence-dependent setup times (PFSP-BS).•A new acceleration method to compute makespan for each solution in the insertion neighbourhood.•A ...constraint-guided local search algorithm to solve PFSP-BS instances.•Comprehensive numerical and statistical tests to evaluate the proposed methods.
Permutation flowshop scheduling problem (PFSP) is a classical NP-Hard combinatorial optimisation problem. Existing PFSP variants capture different realistic scenarios, but significant modelling gaps still remain with respect to many real-world industrial applications. Inspired by the cider industry, in this paper, we propose a new PFSP variant that generalises over simultaneous use of several types of blocking constraints and various settings of sequence-dependent setup times. We also present a computational model for makespan minimisation of the new variant and show that solving this variant remains NP-Hard. For this PFSP variant, we then present an acceleration method to compute makespan efficiently and thus evaluate the neighbourhoods generated by insertion operators. We develop a new constructive heuristic taking both blocking constraints and setup times into account. We also develop a new local search algorithm that uses a constraint guided intensification method and a random-path guided diversification method. Our comprehensive experimental results on a set of benchmark instances demonstrate that our proposed algorithms significantly outperform several state-of-the-art adapted algorithms.
•Studying mixed blocking flowshop scheduling problem (MBPFSP).•A new Acceleration method for insertion neighbourhood operator.•A constraint-guided local search algorithm for solving ...MBPFSP.•Comprehensive numerical and statistical tests to evaluate the proposed methods.
Mixed Blocking Permutation Flowshop Scheduling Problem (MBPFSP) with the objective of makespan minimisation is NP-Hard. It has important industrial applications that include the cider production industry. MBPFSP has made some progress in recent years. However, within practical time limits, existing incomplete algorithms still either find low quality solutions or struggle with large problems. One key reason behind this is the typical way of using generic heuristics or metaheuristics that usually lack problem specific structural knowledge. In MBPFSP, a machine could be blocked with the currently finished job until the subsequent machine is available to process the same job. These blocking constraints affect the makespan. So MBPFSP search should naturally take explicit steps to take the blocking constraints into account. Unfortunately, existing research on MBPFSP just uses only the makespan to compare generated solutions, but the search otherwise is not aware of the blocking constraints. Moreover, existing such methods use either an exhaustive or a random neighbourhood generation strategy. In this work, we aim to advance MBPFSP search by better exploiting the problem specific structural knowledge. We use the constraint and the objective functions to obtain such problem specific knowledge and we exploit such knowledge both in a constructive search method and in a local search method. In this paper, we also present an acceleration method to efficiently evaluate insertion-based neighbourhoods of MBPFSP. Our experimental results on three standard testbeds demonstrate that our proposed algorithms significantly improve over existing best-performing algorithms.
•Studying mixed blocking flowshop scheduling problems (MBPFSP).•Makespan and feasibility preserving flowshop reengineering.•Conjoing successive machines to obtain abstract joint machines.•Abstration ...based model simplification to obtain efficiency.•Improves performances of arbitrary MBPFSP algorithms.
Blocking constraints are ubiquitous in machine scheduling. In a flowshop scenario, a machine might get blocked by a job that has just been processed by the same machine. This happens when there is no buffer where the job can temporarily go before the next machine is available to process it. This also happens when two successive machines depend on a mutually exclusive resource to process the same job. In this paper, we show that under certain conditions, two successive machines operating under blocking constraints involving mutually exclusive resources can virtually be treated as a joint machine. Before performing search, we then use this makespan preserving property in reengineering a permutation flowshop. The reengineered flowshop model can actually be used by any arbitrary search algorithm to improve efficiency. We show an example of machine conjoining in the waste treatment industry. We also empirically show that such reengineering helps state-of-the-art flowshop search algorithms obtain significantly better makespan values than when the original model is used. Flowshop reengineering is appealing particularly because it helps obtain a higher abstraction level and any search algorithm can use it as a preprocessing step.
Protein structure prediction (PSP) is essential for drug discovery. PSP involves minimising an unknown scoring function over an astronomical search space. PSP has achieved significant progress ...recently via end-to-end deep learning models that require enormous computational resources and almost all known proteins as training data. In this paper, we develop a conformational search method for PSP based on scoring functions involving geometric constraints learnt by deep learning models. When machine learning models achieve generality and thus obviously loose accuracy, conformational search methods could perform protein-specific fine tuning of the predicted conformations. However, effective conformational sampling in PSP remains a key challenge. Existing conformational search algorithms adopt random selection approaches for neighbor generation and thus greatly depend on luck. We propose a new approach to analyse geometric constraint-based scores, to identify the regions of the current conformations causing inferior scores, and to alter the identified regions to generate neighbour conformations. Our approach prefers informed decisions to random selections from an artificial intelligence perspective. The proposed method also provides promising search guidance as it obtains significant improvements from given initial conformations. On a set of 35 benchmark proteins of varying types and sizes, our algorithm significantly outperforms state-of-the-art PSP search algorithms that use random sampling with a similar scoring function: the improvement is about 1Å better average in root mean square deviation (RMSD) values. Our sample generation approach could be used in other bioinformatics research areas requiring search.
PDF
