Scheduling Algorithm for Minimizing Number of Machines on Identical Parallel Environment with Restricted Processing Time

This paper considers a number of machines minimization scheduling problem with restricted processing time on identical parallel environment. Up to now, some multi-machines scheduling problems, including identical parallel environment etc., have concentrated on minimizing make-span under a fixed number of machines (facilities or resources). However, in real situations, the make-span may be pros-pected by accumulative experiences of expert or desired due-date of customer, etc. So, we treat the make-span with fixed and prospected constant, and focus on scheduling to minimize number of machines with the fixed make-span. For solving the problem, a linear time algorithm based on the bin packing alforithm is proposed and its validity is discussed. In addition, by supposing the make-span with decision variable, we consider a bi-objective problem to minimize number of machines and desired make-span, simultaneously. For solving the above problem, we propose an efficient algorithm based on a bin packing algorithm and binary search