Computer-aided process planning(CAPP) is an essential component of computer integrated manufacturing(CIM) system. A good process plan can be obtained by optimizing two elements,namely,operation sequence and the machining parameters of machine,tool and tool access direction(TAD) for each operation. This paper proposes a novel optimization strategy for process planning that considers different dimensions of the problem in parallel. A multi-dimensional tabu search(MDTS) algorithm based on this strategy is developed to optimize the four dimensions of a process plan,namely,operation sequence(OperSeq),machine sequence(MacSeq),tool sequence(ToolSeq) and tool approach direction sequence(TADSeq),sequentially and iteratively. In order to improve its efficiency and stability,tabu search,which is incorporated into the proposed MDTS algorithm,is used to optimize each component of a process plan,and some neighbourhood strategies for different components are presented for this tabu search algorithm. The proposed MDTS algorithm is employed to test four parts with different numbers of operations taken from the literature and compared with the existing algorithms like genetic algorithm(GA),simulated annealing(SA),tabu search(TS) and particle swarm optimization(PSO) . Experimental results show that the developed algorithm outperforms these algorithms in terms of solution quality and efficiency. Computer-aided process planning (CAPP) is an essential component of computer integrated manufacturing (CIM) system. A good process plan can be obtained by optimizing two elements, namely, operation sequence and the machining parameters of machine, tool and tool access direction TAD) for each operation. This paper proposes a novel optimization strategy for process planning that considers different dimensions of the problem in parallel. A multi-dimensional tabu search (MDTS) algorithm based on this strategy is developed to optimize the four dimensions of a process order, sequence operation (OseSeq), machine sequence (MacSeq), tool sequence (ToolSeq) and tool approach direction sequence (TADSeq), sequentially and iteratively. In order to improve its efficiency and stability, tabu search, which is incorporated into the proposed MDTS algorithm, is used to optimize each component of a process plan, and some neighborhood strategies for different components are presented for this tabu search algorithm. The proposed MDTS algorithm is employed to test four parts with different numbers of operations taken from the literature and compared with the existing algorithms like genetic algorithm (GA), simulated annealing (SA), tabu search (TS) and particle swarm optimization (PSO) . Experimental results show that the developed algorithm outperforms these algorithms in terms of solution quality and efficiency.