| The problems investigated in this research are the deterministic scheduling of independent jobs on identical machines. A job can be processed on one or more machines simultaneously and the number of machines occupied by a job may change from time to time. The models differ from the classical simultaneous problems in which it is assumed that the number of machines used by a job is fixed during its processing. The processing of a job or a piece of a job in all the proposed problems can also have preemptions. Associated with a job are an arbitrary processing time, release time and/or deadline. All data are integers. Some feasibility problems and minimization problems are explored. An algorithm is presented to check the feasibility for a given set of jobs with release time and deadline constraints and with a strategy of splittings by computing the reservations and surpluses of available machine times. A polynomial algorithm based on the concept of indifference group is proposed to minimize the sum of completion times for a set of jobs with splitting numbers being either 1 or 0 on two machines. For the problem of finding a feasible schedule with a minimum total number of splittings for a given feasible set of jobs with arbitrary deadlines, two algorithms are presented to find upper bound, one is an on-line algorithm and the other is an approximation to an integer programming problem. Finally, the non-simultaneous preemptive problem of minimizing total completion times of a feasible set of jobs with arbitrary deadlines on m identical machines is discussed. Two polynomial algorithms are proposed to find the optimal schedule. All the algorithms can be implemented on microcomputers for most practical applications. |
