An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem
This paper proposes an iterated greedy algorithm for scheduling jobs in F parallel flow shops (lines), each consisting of a series of m machines without storage capacity between machines. This constraint can provoke the blockage of machines if a job has finished its operation and the next machine is...
| Autores: | ; ; |
|---|---|
| Tipo de documento: | Artículo |
| Fecha de publicación: | 2019 |
| País: | España |
| Institución: | Universitat Politècnica de Catalunya (UPC) |
| Repositorio: | UPCommons. Portal del coneixement obert de la UPC |
| Lenguaje: | Inglés |
| OAI Identifier: | oai:upcommons.upc.edu:2117/127883 |
| Acceso en línea: | https://hdl.handle.net/2117/127883 https://dx.doi.org/10.1016/j.eswa.2018.12.039 |
| Nivel de acceso: | Acceso abierto |
| Palabra clave: | Heuristic algorithms Industrial management Parallel flow shop Distribution flow shop Blocking Scheduling Total tardiness Empreses -- Direcció i administració Programació heurística Àrees temàtiques de la UPC::Economia i organització d'empreses |
| _version_ | 1878730481959174144 |
|---|---|
| author | Ribas Vila, Immaculada|||0000-0002-3701-118X |
| author2 | Companys Pascual, Ramón Tort Martorell, X. |
| author2_role | author author |
| author_browse | Companys Pascual, Ramón Ribas Vila, Immaculada|||0000-0002-3701-118X Tort Martorell, X. |
| author_facet | Ribas Vila, Immaculada|||0000-0002-3701-118X Companys Pascual, Ramón Tort Martorell, X. |
| author_role | author |
| collection | UPCommons. Portal del coneixement obert de la UPC |
| description | This paper proposes an iterated greedy algorithm for scheduling jobs in F parallel flow shops (lines), each consisting of a series of m machines without storage capacity between machines. This constraint can provoke the blockage of machines if a job has finished its operation and the next machine is not available. The criterion considered is the minimization of the sum of tardiness of all the jobs to schedule, i.e., minimization of the total tardiness of jobs. Notice that the proposed method is also valid for solving the Distributed Permutation Blocking Flow Shop Scheduling Problem (DBFSP), which allows modelling the scheduling process in companies with more than one factory when each factory has an identical flow shop configuration. Firstly, several constructive procedures have been implemented and tested to provide an efficient solution in terms of quality and CPU time. This initial solution is later improved upon with an iterated greedy algorithm that includes a variable neighbourhood search for interchanging or reassigning jobs from the critical line to other lines. Next, two strategies have been tested for selecting the critical line; the one with a higher total tardiness of jobs and the one with a job that has the highest tardiness. The experimental design chooses the best combination of initial solution and critical line selection. Finally, we compare the performance of the proposed algorithm against other benchmark algorithms proposed for the DPFSP, which have been adapted to the problem being considered here since, to the best of our knowledge, this is the first attempt to solve either the Parallel Blocking Flow Shop problem or the Distributed Blocking Flow Shop problem with the goal of minimizing total tardiness. This comparison has allowed us to confirm the good performance of the proposed method. |
| eu_rights_str_mv | openAccess |
| format | article |
| id | ES_1d28ed6529ca4fc786bbc20f8fb33786 |
| institution | Universitat Politècnica de Catalunya (UPC) |
| instname_str | Universitat Politècnica de Catalunya (UPC) |
| language | eng |
| network_acronym_str | ES |
| network_name_str | España |
| oai_identifier_str | oai:upcommons.upc.edu:2117/127883 |
| publishDate | 2019 |
| publishDateSort | 2019 |
| reponame_str | UPCommons. Portal del coneixement obert de la UPC |
| spelling | An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem Ribas Vila, Immaculada|||0000-0002-3701-118X Companys Pascual, Ramón Tort Martorell, X. Heuristic algorithms Industrial management Parallel flow shop Distribution flow shop Blocking Scheduling Total tardiness Empreses -- Direcció i administració Programació heurística Àrees temàtiques de la UPC::Economia i organització d'empreses This paper proposes an iterated greedy algorithm for scheduling jobs in F parallel flow shops (lines), each consisting of a series of m machines without storage capacity between machines. This constraint can provoke the blockage of machines if a job has finished its operation and the next machine is not available. The criterion considered is the minimization of the sum of tardiness of all the jobs to schedule, i.e., minimization of the total tardiness of jobs. Notice that the proposed method is also valid for solving the Distributed Permutation Blocking Flow Shop Scheduling Problem (DBFSP), which allows modelling the scheduling process in companies with more than one factory when each factory has an identical flow shop configuration. Firstly, several constructive procedures have been implemented and tested to provide an efficient solution in terms of quality and CPU time. This initial solution is later improved upon with an iterated greedy algorithm that includes a variable neighbourhood search for interchanging or reassigning jobs from the critical line to other lines. Next, two strategies have been tested for selecting the critical line; the one with a higher total tardiness of jobs and the one with a job that has the highest tardiness. The experimental design chooses the best combination of initial solution and critical line selection. Finally, we compare the performance of the proposed algorithm against other benchmark algorithms proposed for the DPFSP, which have been adapted to the problem being considered here since, to the best of our knowledge, this is the first attempt to solve either the Parallel Blocking Flow Shop problem or the Distributed Blocking Flow Shop problem with the goal of minimizing total tardiness. This comparison has allowed us to confirm the good performance of the proposed method. Peer Reviewed https://hdl.handle.net/2117/127883 https://dx.doi.org/10.1016/j.eswa.2018.12.039 |
| spellingShingle | An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem Ribas Vila, Immaculada|||0000-0002-3701-118X Heuristic algorithms Industrial management Parallel flow shop Distribution flow shop Blocking Scheduling Total tardiness Empreses -- Direcció i administració Programació heurística Àrees temàtiques de la UPC::Economia i organització d'empreses |
| title | An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem |
| title_full | An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem |
| title_fullStr | An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem |
| title_full_unstemmed | An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem |
| title_short | An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem |
| title_sort | An iterated greedy algorithm for solving the total tardiness parallel blocking flow shop scheduling problem |
| topic | Heuristic algorithms Industrial management Parallel flow shop Distribution flow shop Blocking Scheduling Total tardiness Empreses -- Direcció i administració Programació heurística Àrees temàtiques de la UPC::Economia i organització d'empreses |
| topic_facet | Heuristic algorithms Industrial management Parallel flow shop Distribution flow shop Blocking Scheduling Total tardiness Empreses -- Direcció i administració Programació heurística Àrees temàtiques de la UPC::Economia i organització d'empreses |
| url | https://hdl.handle.net/2117/127883 https://dx.doi.org/10.1016/j.eswa.2018.12.039 |