QIAUJournal of Optimization in Industrial Engineering2251-9904Articles in Press20180201Parallel Jobs Scheduling with a Specific Due Date: Asemi-definite Relaxation-based Algorithm53802410.22094/joie.2017.599.1385ENJavad BehnamianDepartment of Industrial Engineering, Faculty of Engineering, Bu-Ali Sina University, Hamedan, IranJournal Article20160313This paper considers a different version of the parallel machines scheduling problem in which the parallel jobs simultaneously requirea pre-specifiedjob-dependent number of machines when being processed.This relaxation departs from one of the classic scheduling assumptions. While the analytical conditions can be easily statedfor some simple models, a graph model approach is required when conflicts of processor usage are present. The main decisions and solving steps are as follows, respectively.<br /> <em>(i) </em>Converting the scheduling problem to graph model;<br /> <em>(ii) </em>Dividing jobs into independent sets: in this phase, we propose a semi-definite relaxation algorithm in which we use graph coloring concept;<br /> <em>(iii) </em>Sequencing the independent sets as a single-machine scheduling in which jobs in such a system arejob sets formed by using a semi-definite relaxation solution and determining the problem as a schedule that minimizes the sum of the tardiness of jobs.<br /> In this regard, after grouping the jobs by a semi-definite programming relaxation algorithm, we used the rounding algorithm for graph coloring. We also proposed a variable neighborhood search algorithm for sequencing the obtained job sets in order to minimize the sum of the tardiness. Experimental results show that this methodology is interesting by obtaining good results.