Scheduling Trains with Priorities : a no-wait blocking parallel-machine job-shop scheduling model

The paper investigates train scheduling problems when prioritised trains and non-prioritised trains are simultaneously traversed in a single-line rail network. In this case, no-wait conditions arise because the prioritised trains such as express passenger trains should traverse continuously without any interruption. In comparison, non-prioritised trains such as freight trains are allowed to enter the next section immediately if possible or to remain in a section until the next section on the routing becomes available, which is thought of as a relaxation of no-wait conditions. With thorough analysis of the structural properties of the No-Wait Blocking Parallel-Machine Job-Shop-Scheduling (NWBPMJSS) problem that is originated in this research, an innovative generic constructive algorithm (called NWBPMJSS_Liu-Kozan) is proposed to construct the feasible train timetable in terms of a given order of trains. In particular, the proposed NWBPMJSS_Liu-Kozan constructive algorithm comprises several recursively-used sub-algorithms (i.e. Best-Starting-Time-Determination Procedure, Blocking-Time-Determination Procedure, Conflict-Checking Procedure, Conflict-Eliminating Procedure, Tune-up Procedure and Fine-tune Procedure) to guarantee feasibility by satisfying the blocking, no-wait, deadlock-free and conflict-free constraints. A two-stage hybrid heuristic algorithm (NWBPMJSS_Liu-Kozan-BIH) is developed by combining the NWBPMJSS_Liu-Kozan constructive algorithm and the Best-Insertion-Heuristic (BIH) algorithm to find the preferable train schedule in an efficient and economical way. Extensive computational experiments show that the proposed methodology is promising because it can be applied as a standard and fundamental toolbox for identifying, analysing, modelling and solving real-world scheduling problems.

A hybrid shifting bottleneck procedure algorithm for the parallel-machine job-shop scheduling problem

In practice, parallel-machine job-shop scheduling (PMJSS) is very useful in the development of standard modelling approaches and generic solution techniques for many real-world scheduling problems. In this paper, based on the analysis of structural properties in an extended disjunctive graph model, a hybrid shifting bottleneck procedure (HSBP) algorithm combined with Tabu Search metaheuristic algorithm is developed to deal with the PMJSS problem. The original-version SBP algorithm for the job-shop scheduling (JSS) has been significantly improved to solve the PMJSS problem with four novelties: i) a topological-sequence algorithm is proposed to decompose the PMJSS problem into a set of single-machine scheduling (SMS) and/or parallel-machine scheduling (PMS) subproblems; ii) a modified Carlier algorithm based on the proposed lemmas and the proofs is developed to solve the SMS subproblem; iii) the Jackson rule is extended to solve the PMS subproblem; iv) a Tabu Search metaheuristic algorithm is embedded under the framework of SBP to optimise the JSS and PMJSS cases. The computational experiments show that the proposed HSBP is very efficient in solving the JSS and PMJSS problems.

Optimising a coal rail network under capacity constraints

This research deals with an innovative methodology for optimising the coal train scheduling problem. Based on our previously published work, generic solution techniques are developed by utilising a “toolbox” of standard well-solved standard scheduling problems. According to our analysis, the coal train scheduling problem can be basically modelled a Blocking Parallel-Machine Job-Shop Scheduling (BPMJSS) problem with some minor constraints. To construct the feasible train schedules, an innovative constructive algorithm called the SLEK algorithm is proposed. To optimise the train schedule, a three-stage hybrid algorithm called the SLEK-BIH-TS algorithm is developed based on the definition of a sophisticated neighbourhood structure under the mechanism of the Best-Insertion-Heuristic (BIH) algorithm and Tabu Search (TS) metaheuristic algorithm. A case study is performed for optimising a complex real-world coal rail system in Australia. A method to calculate the lower bound of the makespan is proposed to evaluate results. The results indicate that the proposed methodology is promising to find the optimal or near-optimal feasible train timetables of a coal rail system under network and terminal capacity constraints.

Scheduling a flow-shop with combined buffer conditions

In this paper, No-Wait, No-Buffer, Limited-Buffer, and Infinite-Buffer conditions for the flow-shop problem (FSP) have been investigated. These four different buffer conditions have been combined to generate a new class of scheduling problem, which is significant for modelling many real-world scheduling problems. A new heuristic algorithm is developed to solve this strongly NP-hard problem. Detailed numerical implementations have been analysed and promising results have been achieved.

Metaheuristics for minimizing the makespan of the dynamic shop scheduling problem

For the shop scheduling problems such as flow-shop, job-shop, open-shop, mixed-shop, and group-shop, most research focuses on optimizing the makespan under static conditions and does not take into consideration dynamic disturbances such as machine breakdown and new job arrivals. We regard the shop scheduling problem under static conditions as the static shop scheduling problem, while the shop scheduling problem with dynamic disturbances as the dynamic shop scheduling problem. In this paper, we analyze the characteristics of the dynamic shop scheduling problem when machine breakdown and new job arrivals occur, and present a framework to model the dynamic shop scheduling problem as a static group-shop-type scheduling problem. Using the proposed framework, we apply a metaheuristic proposed for solving the static shop scheduling problem to a number of dynamic shop scheduling benchmark problems. The results show that the metaheuristic methodology which has been successfully applied to the static shop scheduling problems can also be applied to solve the dynamic shop scheduling problem efficiently.

A fast tabu search algorithm for the group shop scheduling problem

Three types of shop scheduling problems, the flow shop, the job shop and the open shop scheduling problems, have been widely studied in the literature. However, very few articles address the group shop scheduling problem introduced in 1997, which is a general formulation that covers the three above mentioned shop scheduling problems and the mixed shop scheduling problem. In this paper, we apply tabu search to the group shop scheduling problem and evaluate the performance of the algorithm on a set of benchmark problems. The computational results show that our tabu search algorithm is typically more efficient and faster than the other methods proposed in the literature. Furthermore, the proposed tabu search method has found some new best solutions of the benchmark instances.

Metaheuristics for the mixed shop scheduling problem

In this paper, three metaheuristics are proposed for solving a class of job shop, open shop, and mixed shop scheduling problems. We evaluate the performance of the proposed algorithms by means of a set of Lawrence’s benchmark instances for the job shop problem, a set of randomly generated instances for the open shop problem, and a combined job shop and open shop test data for the mixed shop problem. The computational results show that the proposed algorithms perform extremely well on all these three types of shop scheduling problems. The results also reveal that the mixed shop problem is relatively easier to solve than the job shop problem due to the fact that the scheduling procedure becomes more flexible by the inclusion of more open shop jobs in the mixed shop.

A comparative study of algorithms for the flowshop scheduling problem

In this paper, we propose three meta-heuristic algorithms for the permutation flowshop (PFS) and the general flowshop (GFS) problems. Two different neighborhood structures are used for these two types of flowshop problem. For the PFS problem, an insertion neighborhood structure is used, while for the GFS problem, a critical-path neighborhood structure is adopted. To evaluate the performance of the proposed algorithms, two sets of problem instances are tested against the algorithms for both types of flowshop problems. The computational results show that the proposed meta-heuristic algorithms with insertion neighborhood for the PFS problem perform slightly better than the corresponding algorithms with critical-path neighborhood for the GFS problem. But in terms of computation time, the GFS algorithms are faster than the corresponding PFS algorithms.

Performance and scalability assessment for non-certificate-based public key management in VANETS

Current research in secure messaging for Vehicular Ad hoc Networks (VANETs) appears to focus on employing a digital certificate-based Public Key Cryptosystem (PKC) to support security. The security overhead of such a scheme, however, creates a transmission delay and introduces a time-consuming verification process to VANET communications. This paper proposes a non-certificate-based public key management for VANETs. A comprehensive evaluation of performance and scalability of the proposed public key management regime is presented, which is compared to a certificate-based PKC by employing a number of quantified analyses and simulations. Not only does this paper demonstrate that the proposal can maintain security, but it also asserts that it can improve overall performance and scalability at a lower cost, compared to the certificate-based PKC. It is believed that the proposed scheme will add a new dimension to the key management and verification services for VANETs.

Compact multiport antenna with isolated ports

The small element spacing of compact multiport arrays introduces strong mutual coupling between the antenna ports. Due to this coupling, the input impedance of the array changes when elements excitations are varied, and consequently, the array cannot be matched for an arbitrary excitation. Decoupling networks have in the past been used to provide an additional connection between antenna ports in order to cancel the coupling between elements. An alternative approach is to design the antenna so that each port does not excite a single element, but all elements simultaneously instead. The geometry of the antenna is optimized so that this direct excitation of elements counteracts the mutual coupling, thus yielding decoupled ports. This paper describes the design of such a 4-port antenna.

UWB antenna array for wireless transmission along corridors

A 2-element elliptical patch antenna array with a bi-directional radiation pattern has been developed for ultra wideband indoor wireless communications. The array is constructed by means of feeding two omni-directional elliptical patch elements with a 3-section hybrid power divider. Experimental results show that the array has a stable radiation pattern and low return loss over a broad bandwidth of 64% (3.1 - 6 GHz).

Integrating efficient filtration and visible-light photocatalysis by loading Ag-doped zeolite Y particles on aluminia nanofiber membrane

Filtration membrane technology has already been employed to remove various organic effluents produced from the textile, paper, plastic, leather, food and mineral processing industries. To improve membrane efficiency and alleviate membrane fouling, an integrated approach is adopted that combines membrane filtration and photocatalysis technology. In this study, alumina nanofiber (AF) membranes with pore size of about 10 nm (determined by the liquid-liquid displacement method) have been synthesized through an in situ hydrothermal reaction, which permitted a large flux and achieved high selectivity. Silver nanoparticles (Ag NPs) are subsequently doped on the nanofibers of the membranes. Silver nanoparticles can strongly absorb visible light due to the surface plasmon resonance (SPR) effect, and thus induce photocatalytic degradation of organic dyes, including anionic, cationic and neutral dyes, under visible light irradiation. In this integrated system, the dyes are retained on the membrane surface, their concentration in the vicinity of the Ag NPs are high and thus can be efficiently decomposed. Meanwhile, the usual flux deterioration caused by the accumulation of the filtered dyes in the passage pores can be avoided. For example, when an aqueous solution containing methylene blue is processed using an integrated membrane, a large flux of 200 L m-2 h-1 and a stable permeating selectivity of 85% were achieved. The combined photocatalysis and filtration function leads to superior performance of the integrated membranes, which have a potential to be used for the removal of organic pollutants in drinking water.

Hydrothermal synthesis of single crystallin strontium titanate nanocubes

Strontium titanate nanocubes with an average edge length of 150mm have been successfully synthesized from a simple hydrothermal system. Characterization techniques such as X-ray powder diffraction analysis, scanning electron microscopy and energy-dispersive analysis of X-rays were used to investigate the products. The results showed that as-prepared powders are pure SrTiO3 with cubic shape, which consists with the growth habit of its intrinsic crystal structure. These uniform nanocubes with high crystallinity will exhibit superior physical properties in the practical applications. Furthermore, during the experimental process, it has been found that the dilute acid washing process is very important to obtain high pure SrTiO3.

Phenotypic characterization of osteoarthritic osteocytes from the sclerotic zones : a possible pathological role in subchondral bone sclerosis

Subchondral bone sclerosis is a well-recognised manifestation of osteoarthritis (OA). The osteocyte cell network is now considered to be central to the regulation of bone homeo-stasis; however, it is not known whether the integrity of the osteocyte cell network is altered in OA patients. The aim of this study was to investigate OA osteocyte phenotypic changes and its potential role in OA subchondral bone pathogenesis. The morphological and phenotypic changes of osteocytes in OA samples were investigated by micro-CT, SEM, histology, im-munohistochemistry, TRAP staining, apoptosis assay and real-time PCR studies. We demonstrated that in OA subchondral bone, the osteocyte morphology was altered showing rough and rounded cell body with fewer and disorganized dendrites compared with the os-teocytes in control samples. OA osteocyte also showed dysregulated expression of osteocyte markers, apoptosis, and degradative enzymes, indicating that the phenotypical changes in OA osteocytes were accompanied with OA subchondral bone remodelling (increased osteoblast and osteoclast activity) and increased bone volume with altered mineral content. Significant alteration of osteocytes identified in OA samples indicates a potential regulatory role of osteocytes in subchondral bone remodelling and mineral metabolism during OA pathogene-sis.