Graph colouring-based algorithm to parallel jobs scheduling on parallel factories. Issue 6 (2nd June 2016)

• Record Type: Journal Article
• Authors: Behnamian, J.
• Is Part Of: International journal of computer integrated manufacturing. Volume 29:Issue 6(2016)
• Page Start: 622
• Page End: 635
• Publication Date: 2016-06-02
• Subjects: distributed scheduling -- parallel machines -- parallel jobs -- graph colouring -- semidefinite programming; Computer integrated manufacturing systems -- Periodicals; 670.427
• DOI: 10.1080/0951192X.2015.1099074
• Languages: English
• ISSNs: 0951-192X

Abstract

Abstract : This paper studies the multi-factory scheduling problem where a number of different individual factories join together to form a production network. In this problem, it is assumed each job has an original factory that initially ordered it, jobs can transport between the different factories in overloaded situations and the speed of machines in each factory can be different. Here, it is also assumed that the jobs may use more than one machine at the same time which is known as parallel jobs scheduling. This research extends a two-phase algorithm. In the first phase, the jobs according to need of machines decompose into the several job sets via semidefinite programming and a rounding algorithm in the graph. Then, in the second phase for scheduling the job sets obtained from first phase, we propose a discrete particle swarm optimisation (PSO). Finally, an extensive numerical study is conducted to assess the performance of proposed algorithm.