The current implementation of the WsCleanup publisher is using BuildStepMonitor.STEP as value for the getRequiredMonitorService method. This forces Jenkins to wait previous build to complete this step before running it in latest build. As this plugin does not seem to rely on any Action from previous builds adviced value is BuildStepMonitor.NONE (http://javadoc.jenkins-ci.org/hudson/tasks/BuildStep.html#getRequiredMonitorService()).

This bug is pretty annoying as it serializes a large set of our builds, which should complete independently.