Estimation of Distribution Algorithms (EDAs) use a probabilistic model of promising solutions found so far to obtain new candidate solutions of an optimization problem. This paper focuses on the design of parallel EDAs. More specifically, the paper describes a method for parallel construction of Bayesian networks with local structures in form of decision trees in the Mixed Bayesian Optimization Algorithm. The proposed Multithreaded Mixed Bayesian Optimization Algorithm (MMBOA) is intended for implementation on a cluster of workstations that communicate by Message Passing Interface (MPI). Communication latencies between workstations are eliminated by multithreaded processing, so in each workstation the high-priority model-building thread, which is communication demanding, can be overlapped by low-priority model sampling thread when necessary. High performance of MMBOA is verified via simulation in TRANSIM tool.