A Job-Shop Scheduling Problem with Bidirectional Circular Precedence Constraints

This paper introduces a job-shop scheduling problem (JSP) with bidirectional circular precedence constraints, called BCJSP. In the problem, each job can be started from any operation and continued by its remaining operations in a circular precedence-relation chain via either a clockwise or countercl...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Pisut Pongchairerks
Formato:	article
Lenguaje:	EN
Publicado:	Hindawi-Wiley 2021
Materias:	Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/7c095aa3cccf4e8a9fc5af3bd922bbec
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:7c095aa3cccf4e8a9fc5af3bd922bbec
record_format	dspace
spelling	oai:doaj.org-article:7c095aa3cccf4e8a9fc5af3bd922bbec2021-11-22T01:10:52ZA Job-Shop Scheduling Problem with Bidirectional Circular Precedence Constraints1099-052610.1155/2021/3237342https://doaj.org/article/7c095aa3cccf4e8a9fc5af3bd922bbec2021-01-01T00:00:00Zhttp://dx.doi.org/10.1155/2021/3237342https://doaj.org/toc/1099-0526This paper introduces a job-shop scheduling problem (JSP) with bidirectional circular precedence constraints, called BCJSP. In the problem, each job can be started from any operation and continued by its remaining operations in a circular precedence-relation chain via either a clockwise or counterclockwise direction. To solve BCJSP, this paper proposes a multilevel metaheuristic consisting of top-, middle-, and bottom-level algorithms. The top- and middle-level algorithms are population-based metaheuristics, while the bottom-level algorithm is a local search algorithm. The top-level algorithm basically controls a start operation and an operation-precedence-relation direction of each job, so that BCJSP becomes a JSP instance that is a subproblem of BCJSP. Moreover, the top-level algorithm can also be used to control input parameters of the middle-level algorithm, as an optional extra function. The middle-level algorithm controls input parameters of the bottom-level algorithm, and the bottom-level algorithm then solves the BCJSP’s subproblem. The middle-level algorithm evolves the bottom-level algorithm’s parameter values by using feedback from the bottom-level algorithm. Likewise, the top-level algorithm evolves the start operations, the operation-precedence-relation directions, and the middle-level algorithm’s parameter values by using feedback from the middle-level algorithm. Performance of two variants of the multilevel metaheuristic (i.e., with and without the mentioned extra function) was evaluated on BCJSP instances modified from well-known JSP instances. The variant with the extra function performs significantly better in number than the other. The existing JSP-solving algorithms can also solve BCJSP; however, their results on BCJSP are clearly worse than those of the two variants of the multilevel metaheuristic.Pisut PongchairerksHindawi-WileyarticleElectronic computers. Computer scienceQA75.5-76.95ENComplexity, Vol 2021 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Electronic computers. Computer science QA75.5-76.95
spellingShingle	Electronic computers. Computer science QA75.5-76.95 Pisut Pongchairerks A Job-Shop Scheduling Problem with Bidirectional Circular Precedence Constraints
description	This paper introduces a job-shop scheduling problem (JSP) with bidirectional circular precedence constraints, called BCJSP. In the problem, each job can be started from any operation and continued by its remaining operations in a circular precedence-relation chain via either a clockwise or counterclockwise direction. To solve BCJSP, this paper proposes a multilevel metaheuristic consisting of top-, middle-, and bottom-level algorithms. The top- and middle-level algorithms are population-based metaheuristics, while the bottom-level algorithm is a local search algorithm. The top-level algorithm basically controls a start operation and an operation-precedence-relation direction of each job, so that BCJSP becomes a JSP instance that is a subproblem of BCJSP. Moreover, the top-level algorithm can also be used to control input parameters of the middle-level algorithm, as an optional extra function. The middle-level algorithm controls input parameters of the bottom-level algorithm, and the bottom-level algorithm then solves the BCJSP’s subproblem. The middle-level algorithm evolves the bottom-level algorithm’s parameter values by using feedback from the bottom-level algorithm. Likewise, the top-level algorithm evolves the start operations, the operation-precedence-relation directions, and the middle-level algorithm’s parameter values by using feedback from the middle-level algorithm. Performance of two variants of the multilevel metaheuristic (i.e., with and without the mentioned extra function) was evaluated on BCJSP instances modified from well-known JSP instances. The variant with the extra function performs significantly better in number than the other. The existing JSP-solving algorithms can also solve BCJSP; however, their results on BCJSP are clearly worse than those of the two variants of the multilevel metaheuristic.
format	article
author	Pisut Pongchairerks
author_facet	Pisut Pongchairerks
author_sort	Pisut Pongchairerks
title	A Job-Shop Scheduling Problem with Bidirectional Circular Precedence Constraints
title_short	A Job-Shop Scheduling Problem with Bidirectional Circular Precedence Constraints
title_full	A Job-Shop Scheduling Problem with Bidirectional Circular Precedence Constraints
title_fullStr	A Job-Shop Scheduling Problem with Bidirectional Circular Precedence Constraints
title_full_unstemmed	A Job-Shop Scheduling Problem with Bidirectional Circular Precedence Constraints
title_sort	job-shop scheduling problem with bidirectional circular precedence constraints
publisher	Hindawi-Wiley
publishDate	2021
url	https://doaj.org/article/7c095aa3cccf4e8a9fc5af3bd922bbec
work_keys_str_mv	AT pisutpongchairerks ajobshopschedulingproblemwithbidirectionalcircularprecedenceconstraints AT pisutpongchairerks jobshopschedulingproblemwithbidirectionalcircularprecedenceconstraints
_version_	1718418347381489664

A Job-Shop Scheduling Problem with Bidirectional Circular Precedence Constraints

Ejemplares similares