Cooperative and non-cooperative algorithms for distributed parallel jobs scheduling

Javad Behnamian ()
Additional contact information
Javad Behnamian: Bu-Ali Sina University

Flexible Services and Manufacturing Journal, 2024, vol. 36, issue 1, No 6, 174 pages

Abstract: Abstract This paper deals with multi-factory parallel job scheduling in which independent factories try to satisfy market demand by cooperating with each other. In parallel job scheduling, unlike classical scheduling, jobs require a pre-specified job-dependent number of machines simultaneously when being processed. In the research, although it is assumed that the factories operate separately, in some cases, due to a large number of orders in one factory, some jobs may be sent to other factories to minimize the total completion time of jobs taking into account transportation time. In other words, in this system, it is assumed that each factory, after satisfying the demand of its region, can cooperate with other factories in order to achieve a better objective function for the production network. In the first step of the proposed approach, after associating the scheduling system with a constrained graph, a semidefinite programming rounding and a heuristic are proposed to color the graph in small and large-size instances, respectively. Finally, in the first step, it is shown that the problem under study can be reduced to a parallel machine scheduling problem. Given the heterogeny of factories, in the next step, mixed-integer linear programming, as well as two heuristic algorithms, are proposed. The comparison results of the proposed algorithm, imperialist competitive algorithm and the non-cooperative local scheduling algorithm show that the two-phase cooperative distributed algorithm is quite efficient.

Keywords: Scheduling; Distributed system; Parallel job; Heuristic algorithm; Graph coloring (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10696-022-09469-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:flsman:v:36:y:2024:i:1:d:10.1007_s10696-022-09469-4

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10696

DOI: 10.1007/s10696-022-09469-4

Access Statistics for this article

Flexible Services and Manufacturing Journal is currently edited by Hans Günther

More articles in Flexible Services and Manufacturing Journal from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().