We are working on a machining line balancing problem involving specific constraints. The studied lines are paced and serial, i.e. a part to be machined passes through a sequence of stations. The stations are equipped with CNC (Computer Numerical Control) machines. A CNC machine is a mono-spindle head machine which can use sequentially different tools and can rotate the part in order to perform different tasks. Such a machine is guided by a computer numerical controller system. As usual with machining lines, this problem is subject to precedence constraints as well as exclusion and inclusion constraints. Moreover, the station workload depends on the sequence in which the tasks are assigned because of set-up times related to the change and displacement of tools, rotation of the part, etc. In addition, accessibility constraints have to be considered. Two types of CNC machines with different characteristics can be used. Several tasks require a particular type of machine. The objective is to assign a given set of tasks, required for part machining, as well as a given set of machines to a sequence of stations while minimizing the total cost of the line. In this paper, a multi-start heuristic is proposed and tested on real life industrial problems.