Scheduling of Identical Parallel Machines under Availability Constraint

Abstract

Abstract : Resource planning, optimizing resource utilization and cost, is important in industrial operation management. The domain of scheduling is extremely broad, including many fields like manufacturing, planning, time tabling, project management, software engineering, transportation, CPU job scheduling, cloud computing, service scheduling etc. Resources and machines are subject to availability. The objective of this study is to develop algorithms to schedule jobs on parallel machines with target the minimization of the completion time. The jobs are resumable and arbitrary preemtion is permitted. This problem is considered a hard combinatorial problem and approximating techniques will be used to solve it. The mixed integer quadratic programming will be introduced to solve the small size problems optimally and a constructive greedy algorithm will be introduced to find good feasible solutions. The problem is formulated mathematically and a theoretical lower bound is proved. In addition to that, an absolute performance guaranty provided by a list scheduling algorithm is used to validate the performance of a proposed heuristic. The efficiency of the heuristic will be examined by calculating the distance of the obtained solutions from the lower bound and the value obtained by the list algorithm. For more validation of the new heuristic, we used the modified Graham data set.