Article ID: | iaor20121294 |
Volume: | 39 |
Issue: | 9 |
Start Page Number: | 2258 |
End Page Number: | 2264 |
Publication Date: | Sep 2012 |
Journal: | Computers and Operations Research |
Authors: | Bozejko Wojciech |
Keywords: | combinatorial optimization, computational analysis: parallel computers |
New parallel objective function determination methods for the job shop scheduling problem are proposed in this paper, considering makespan and the sum of jobs execution times criteria, however, the methods proposed can be applied also to another popular objective functions such as jobs tardiness or flow time. Parallel Random Access Machine (PRAM) model is applied for the theoretical analysis of algorithm efficiency. The methods need a fine‐grained parallelization, therefore the approach proposed is especially devoted to parallel computing systems with fast shared memory (e.g. GPGPU,