Branch-and-bound and PSO algorithms for no-wait job shop scheduling

Abdelhakim AitZai (), Brahim Benmedjdoub () and Mourad Boudhar ()
Additional contact information
Abdelhakim AitZai: USTHB University
Brahim Benmedjdoub: USTHB University
Mourad Boudhar: USTHB University

Journal of Intelligent Manufacturing, 2016, vol. 27, issue 3, No 14, 679-688

Abstract: Abstract This paper deals with the no-wait job shop scheduling problem resolution. The problem is to find a schedule to minimize the makespan ( $$C_{max}$$ C m a x ), that is, the total completeness time of all jobs. The no-wait constraint occurs when two consecutive operations in a job must be processed without any waiting time either on or between machines. For this, we have proposed two different resolution methods, the first is an exact method based on the branch-and-bound algorithm, in which we have defined a new technique of branching. The second is a particular swarm optimization (PSO) algorithm, extended from the discrete version of PSO. In the proposed algorithm, we have defined the particle and the velocity structures, and an efficient approach is developed to move a particle to the new position. Moreover, we have adapted the timetabling procedure to find a good solution while respecting the no-wait constraint. Using the PSO method, we have reached good results compared to those in the literature.

Keywords: Scheduling; Job shop; No-wait; Branch-and-bound; PSO (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://link.springer.com/10.1007/s10845-014-0906-7 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:joinma:v:27:y:2016:i:3:d:10.1007_s10845-014-0906-7

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

DOI: 10.1007/s10845-014-0906-7

Access Statistics for this article

Journal of Intelligent Manufacturing is currently edited by Andrew Kusiak

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