Modeling and Solving Scheduling Problem with m Uniform Parallel Machines Subject to Unavailability Constraints  
[PERSON]  
1 College of Information Technology, University of Bahrain, P.O. Box 32038 Manama, Bahrain; [EMAIL_ADDRESS]  
that each machine is unavailable during \(k\) periods in the planning horizon. In the second field, \(\beta\), \(a\) indicates that the machines are subject to availability constraints. Lastly, the third field, \(\gamma\), describes the objective to be minimized, that is, the completion time of the last processed job, denoted by \(C_{max}\).  
Many papers in the literature studied parallel machine-scheduling problems with availability constraints, but very few considered a uniform parallel machine setting. To the best of our knowledge, only two related papers exist so far, [7, 8]. In [7], the authors studied the uniform parallel machine-scheduling problem where each machine could be unavailable during one period of time. The considered performance measures were total completion times and makespan. Two types of jobs were treated, namely, identical and nonidentical jobs. Linear programming models and optimal algorithms were developed to solve the problem where jobs are identical. For the case of nonidentical jobs, the authors proved that the problem is NP-hard, and proposed a quadratic program and a heuristic that were tested on large-sized problem instances. The online version of the problem was studied in [8]. The authors considered the case of two machines under the constraint of one periodically unavailable machine. The identical- and uniform-machine cases were investigated. The objective was to minimize the makespan. The solution approach consisted of optimal algorithms with competitive ratios.  
Furthermore, most research papers studied the case of identical parallel machines. For example, [9, 10, 11, 12, 13] studied various identical parallel machine problems allowing various types of unavailable intervals for machines.  
The shortage in research in this area, and the important applications of the investigated problem in reality motivated the author of this paper to explore this area more and contribute to the scientific research on it. Uniform parallel machine scheduling can be found in the manufacturing field where the same type of job can be processed on new and old machines that have different speeds. As an example, a printing task can take much more time on an old machine than on a new one.  
In this paper, the main contributions are a quadratic programming-model (QM) formulation of a uniform parallel machine with multiple availability constraints and an algorithm that provides optimal solutions. To the best of our knowledge, the proposed QM is the first such formulation for scheduling on uniform parallel machine with availability constraints.  
The content of this paper is organized as follows. Problem notations are laid in Section 2. In Section 3.1, a quadratic model for the problem with makespan as an objective is developed. Section 3.2 details an algorithm proposed for makespan-performance measurement. The proposed algorithm was tested on different problem instances, and results are displayed in Section 4. Finally, a general conclusion is formulated in Section 5.