J2EE is the primary middleware platform for distributed enterprise applications. Current J2EE (Java 2 platform enterprise edition) transaction scheduling to entity beans is still a simple First-Come First-Served (FCFS) policy. Due to this simple policy, transaction manager is unable to distinguish the key tasks from the trivial ones and the performance of the key tasks is reduced when the server’s load is heavy. Since some characteristics of J2EE middleware, the traditional scheduling algorithms can not be applied to J2EE directly. This paper puts forward a scheduling algorithm named TMPBP (threaded multi-queue priority-based protocol). The algorithm includes a heuristic priority assignment algorithm named HRS, which can recognize the key tasks dynamically. TMPBP improves the Quality of Service (QoS) of the key tasks effectively under heavy load. It is safe and has no starvation or priority inversion. The performance experiments indicate that a considerable improvement on QoS of key tasks has been achieved under the proper parameters of the algorithm.