Automated material handling system (AMHS) ensures efficient transport of material from one place to another in the manufacturing area, which is widely adopted to transport wafers in semiconductor manufacturing facilities. Efficient transportation in AMHS is crucial for maintaining manufacturing chain continuity, preventing machine idle time, and reducing cycle times by minimizing waiting time between operations. In this paper, we propose a spatio-temporal conflict elimination search (STCS) algorithm to improve the transportation efficiency of AMHS, which incorporates a job dispatching strategy based on global vehicle movement and idle vehicle management based on a triggered move least policy. Besides, STCS resolves the collisions of vehicles at merge nodes by a spatio-temporal elimination method. Simulation experiments on real-world fab data show that the STCS algorithm achieves competitive performance regarding to the production efficiency and vehicle utilization. Some key features are analyzed to identify the intrinsic properties of AMHS, which encourages decision-makers to adopt proper configuration in different manners to reduce costs and improve efficiency.

In a local search algorithm, one of its most important features is the definition of its neighborhood which is crucial to the algorithm’s performance. In this paper, we present an analysis of neighborhood combination search for solving the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness (SMSWT). First, We propose a new neighborhood structure named Block Swap (B1) which can be considered as an extension of the previously widely used Block Move (B2) neighborhood, and a fast incremental evaluation technique to enhance its evaluation efficiency. Second, based on the Block Swap and Block Move neighborhoods, we present two kinds of neighborhood structures: neighborhood union (denoted by B1 $\cup$B2) and token-ring search (denoted by B1 $\to$B2), both of which are combinations of B1 and B2. Third, we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms: the Iterated Local Search Algorithm ( ${\mathrm{I}\mathrm{L}\mathrm{S}}_{\mathrm{n}\mathrm{e}\mathrm{w}}$) and the Hybrid Evolutionary Algorithm (HEA ${}_{\mathrm{n}\mathrm{e}\mathrm{w}}$) to investigate the performance of the neighborhood union and token-ring search. Extensive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods. Tested on the 120 public benchmark instances, our HEA ${}_{\text{new}}$ has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics. We have also tested the HEA ${}_{\text{new}}$ algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time. HEA ${}_{\text{new}}$ is able to match the optimal or the best known results for all the 64 instances. In particular, the computational time for reaching the best well-known results for five challenging instances is reduced by at least 61.25%.