Scheduling with job rejection and nonsimultaneous machine available time on unrelated parallel machines

•We study an unrelated parallel machine scheduling model with job rejection.•Nonsimultaneous machine available time option is considered.•The objective is to minimize the makespan plus total cost.•We present a heuristic with worst-case ratio bound of 2.

An unrelated-parallel-machine scheduling model with job rejection option was studied. In this model, all jobs are available at time zero but some machines are not available at time zero. Each job is either accepted and processed once without interruption, or is rejected at a penalty cost. To minimize the makespan of all accepted jobs plus the total cost of rejecting and processing jobs, we provide a heuristic with worst-case ratio bound of 2.