Thanks for your clarification. Now I understand your problem much better.
He is right, you need a HardActivityConstraint to enforce this. Working with an ActivityConstraint is what I experienced not that easy. You need to consider all possible states when inserting a new Activity. For example, a state might be the current route state [Start, P1,P2,NP,NP,End]. Then there are actually two allowed insertion positions for an activity of priority P1, between Start and P1 AND between P1 and P2. Thus if prevAct is of type P2 and new act of type P1, your constraint can never be fulfilled anymore and you can break evaluation in this route. When I implement such a constraint, I always start developing an appropriate test suite that mocks all possible states.
Tip: Do not use a HashMap to store your priority labels, but use an appropriate array. This really makes a difference when working with activity constraints (since they are called very frequently).
BTW: If you want to make sure that all jobs with a high priority need to be served as early as possible or to put it in other words, if you want the last high priority job to be served earlier than the first job with medium priority, I doubt that you can achieve this with your approach. You can if you only have one route, but once you have several routes NP jobs might be served earlier in time than P1 jobs, e.g. if you have two valid routes: [P1,P1,P1,P1,P1,P1], [NP,NP]. Then the first NP job will probably served earlier than the last P1 job.