I have been working with Job Scheduler API. For Marshmallow it works perfectly. But for Lollipop Device(5.1.1) it does not starts instantly (takes random number of minutes). What i Mean to say is the onStartJob() method takes some time to invoke.
Following is the code snippet with Which i am scheduling my Job.
private void scheduleJob() {
    ComponentName serviceName = new ComponentName(this, SampleJobService.class);
    JobInfo jobInfo = new JobInfo.Builder(1000, serviceName)
        .setRequiredNetworkType(JobInfo.NETWORK_TYPE_NONE)
        .setRequiresCharging(false)
        .setPeriodic(60 * 1000)
        .build();
    JobScheduler scheduler = (JobScheduler) this.getSystemService(Context.JOB_SCHEDULER_SERVICE);
    int result = scheduler.schedule(jobInfo);
    if (result == JobScheduler.RESULT_SUCCESS) {
        Log.e("khushank", "Job scheduled successfully!");
        Toast.makeText(this, "Job scheduled successfully!", Toast.LENGTH_LONG).show();
    } else {
        Log.e("khushank", "not able to start result: " + result);
    }
}
And following is my Simple Job Service which Just write the logs
public class SampleJobService extends JobService {
    @Override
    public boolean onStartJob(JobParameters params) {
        Log.e("khushank","job started with id = "+params.getJobId());
        return false;
    }
    @Override
    public boolean onStopJob(JobParameters params) {
        Log.e("khushank","job Stopped with id = "+params.getJobId());
        return false;
    }
}
And when i run this sample Application the logs are printed like this :
12-16 16:28:17.040 27119-27119/com.example.inkkashy02.myapplication E/khushank: Job scheduled successfully!
12-16 16:29:17.032 27119-27119/com.example.inkkashy02.myapplication E/khushank: job started with id = 1000
Not able to debug why it takes almost a minute to call onStartJob() in Lollipop. For Marshmallow it gets invoked as soon as job is scheduled. Please tell the root cause of this problem.
                        
A little late to the party, but I found exactly the same issue on my Oppo F1F and Android 5.1.1 - OK on later phones I tested on. I tried network none as well, but even with the following which should force the immediacy it was not:
I read elsewhere minimum latency of 0 would cause this issue, hence set to 1; set override deadline of 1 should be maximum timeout if other constraints have not been met. To be fair I never tried 2. My solution was to just only use jobs from Android 8; I figured bugs ironed out by then! Did you come to any resolution?