{"id":{"repo_id":"vt","oai_identifier":"oai:vtechworks.lib.vt.edu:10919/114608"},"canonical_url":"https://search.dev.ndltd.org/etd/vt/oai:vtechworks.lib.vt.edu:10919/114608","repository":{"repo_id":"vt","name":"Virginia Tech","base_url":"https://vtechworks.lib.vt.edu/oai/request"},"display":{"title":"An analysis tableau and algorithm for flow-shop makespan minimization","abstract":"An analysis tableau suitable for investigating flow-shop attributes is presented in detail 1. Geometric properties, inherent within the tableau, are employed using graph theory concepts in developing a heuristic algorithm for makespan minimization. Computer implementation of this algorithm revealed promising results when compared with several state of-the-art heuristic algorithms. The tableau can be conceived as a three-dimensional matrix with the first two indices consisting of job numbers (rows) and machine numbers (columns). The third index is used to distinguish processing times and accumulative makespan values. The matrix is as informative as the Gantt Chart and yet offers additional advantages when considering the flow-shop problem, such as: 1. Provides an instructional tableau format which is organized, systematic, and directly amenable for hand or digital-computer calculations, 2. Depicts computational contingencies for accumulative makespan values (individual job due-dates as well as flow-shop makespan), 3. Depicts machine and job dominances, 4. Allows for sensitivity analysis {effects of processing times upon accumulative makespan values), 5. Identifies critical-processing times, 6. Reveals where external improvements would be cost effective, 7. Representation is easily modified for job permutations, 8. Representation is not limited to small flow-shops (low number of jobs and/or machines), 9. Allows for additional insight when investigating heuristics, and 10. Can be used as an instructional- , managerial- , and/or a research- tool for analyzing flow-shop attributes. The tableau allows a macro-sensitivity analysis of the entire flow-shop. Specifically, the maximum increase in various processing times, without increasing the flow-shop make span, can be determined. This analysis utilizes graphical representations (segments and nodes) in matrix (tableau). Graphical representation is a convenient means for preserving the history of how each accumulative makespan value was mathematically generated. Concepts such as: partial-paths and critical-paths in conjunction with regions-of-influence are discussed in order to determine the interrelationship between the accumulative makespan values and the processing times, for a specific job sequence.","abstract_html":"An analysis tableau suitable for investigating flow-shop attributes is presented in detail 1. Geometric properties, inherent within the tableau, are employed using graph theory concepts in developing a heuristic algorithm for makespan minimization. Computer implementation of this algorithm revealed promising results when compared with several state of-the-art heuristic algorithms. The tableau can be conceived as a three-dimensional matrix with the first two indices consisting of job numbers (rows) and machine numbers (columns). The third index is used to distinguish processing times and accumulative makespan values. The matrix is as informative as the Gantt Chart and yet offers additional advantages when considering the flow-shop problem, such as: 1. Provides an instructional tableau format which is organized, systematic, and directly amenable for hand or digital-computer calculations, 2. Depicts computational contingencies for accumulative makespan values (individual job due-dates as well as flow-shop makespan), 3. Depicts machine and job dominances, 4. Allows for sensitivity analysis {effects of processing times upon accumulative makespan values), 5. Identifies critical-processing times, 6. Reveals where external improvements would be cost effective, 7. Representation is easily modified for job permutations, 8. Representation is not limited to small flow-shops (low number of jobs and/or machines), 9. Allows for additional insight when investigating heuristics, and 10. Can be used as an instructional- , managerial- , and/or a research- tool for analyzing flow-shop attributes. The tableau allows a macro-sensitivity analysis of the entire flow-shop. Specifically, the maximum increase in various processing times, without increasing the flow-shop make span, can be determined. This analysis utilizes graphical representations (segments and nodes) in matrix (tableau). Graphical representation is a convenient means for preserving the history of how each accumulative makespan value was mathematically generated. Concepts such as: partial-paths and critical-paths in conjunction with regions-of-influence are discussed in order to determine the interrelationship between the accumulative makespan values and the processing times, for a specific job sequence.","abstract_has_math":false,"creators":["McHale, Nancy Ellis"],"institution":"Virginia Polytechnic Institute and State University","degree_name":"M. S.","degree_level":"masters","degree_discipline":"Industrial Engineering and Operations Research","degree_department":"Industrial Engineering and Operations Research","school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":1983,"date_issued":"1983","date_published":"1983","updated_at":"2026-07-22T22:19:04Z","subjects":[],"languages":["en"],"rights":["In Copyright"],"rights_urls":["http://rightsstatements.org/vocab/InC/1.0/"],"identifier_entries":[]},"links":{"outbound_url":"http://hdl.handle.net/10919/114608","outbound_label":"Handle","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor.department","label":"Department","values":["Industrial Engineering and Operations Research"]},{"key":"dc:creator","label":"Author","values":["McHale, Nancy Ellis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2023-04-20T14:53:12Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2023-04-20T14:53:12Z"]},{"key":"dc:date.issued","label":"Date","values":["1983"]},{"key":"dc:publisher","label":"Institution","values":["Virginia Polytechnic Institute and State University"]},{"key":"dc:type","label":"Dc Type","values":["Thesis"]},{"key":"dc:type.dcmitype","label":"Dc Type Dcmitype","values":["Text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Industrial Engineering and Operations Research"]},{"key":"thesis:degree_level","label":"Degree Level","values":["masters"]},{"key":"thesis:degree_name","label":"Degree Name","values":["M. S."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["Virginia Polytechnic Institute and State University"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language.iso","label":"Language (ISO)","values":["en"]},{"key":"dc:rights","label":"Dc Rights","values":["In Copyright"]},{"key":"dc:rights.uri","label":"Rights URI","values":["http://rightsstatements.org/vocab/InC/1.0/"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.uri","label":"Identifier URI","values":["http://hdl.handle.net/10919/114608"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description.abstract","label":"Abstract","values":["An analysis tableau suitable for investigating flow-shop attributes is presented in detail 1. Geometric properties, inherent within the tableau, are employed using graph theory concepts in developing a heuristic algorithm for makespan minimization. Computer implementation of this algorithm revealed promising results when compared with several state of-the-art heuristic algorithms. The tableau can be conceived as a three-dimensional matrix with the first two indices consisting of job numbers (rows) and machine numbers (columns). The third index is used to distinguish processing times and accumulative makespan values. The matrix is as informative as the Gantt Chart and yet offers additional advantages when considering the flow-shop problem, such as: 1. Provides an instructional tableau format which is organized, systematic, and directly amenable for hand or digital-computer calculations, 2. Depicts computational contingencies for accumulative makespan values (individual job due-dates as well as flow-shop makespan), 3. Depicts machine and job dominances, 4. Allows for sensitivity analysis {effects of processing times upon accumulative makespan values), 5. Identifies critical-processing times, 6. Reveals where external improvements would be cost effective, 7. Representation is easily modified for job permutations, 8. Representation is not limited to small flow-shops (low number of jobs and/or machines), 9. Allows for additional insight when investigating heuristics, and 10. Can be used as an instructional- , managerial- , and/or a research- tool for analyzing flow-shop attributes. The tableau allows a macro-sensitivity analysis of the entire flow-shop. Specifically, the maximum increase in various processing times, without increasing the flow-shop make span, can be determined. This analysis utilizes graphical representations (segments and nodes) in matrix (tableau). Graphical representation is a convenient means for preserving the history of how each accumulative makespan value was mathematically generated. Concepts such as: partial-paths and critical-paths in conjunction with regions-of-influence are discussed in order to determine the interrelationship between the accumulative makespan values and the processing times, for a specific job sequence."]},{"key":"dc:description.degree","label":"Dc Description Degree","values":["M. S."]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["An analysis tableau and algorithm for flow-shop makespan minimization"]}]}],"canonical_facts":{"dc:contributor.department":["Industrial Engineering and Operations Research"],"dc:creator":["McHale, Nancy Ellis"],"dc:date.accessioned":["2023-04-20T14:53:12Z"],"dc:date.available":["2023-04-20T14:53:12Z"],"dc:date.issued":["1983"],"dc:description.abstract":["An analysis tableau suitable for investigating flow-shop attributes is presented in detail 1. Geometric properties, inherent within the tableau, are employed using graph theory concepts in developing a heuristic algorithm for makespan minimization. Computer implementation of this algorithm revealed promising results when compared with several state of-the-art heuristic algorithms. The tableau can be conceived as a three-dimensional matrix with the first two indices consisting of job numbers (rows) and machine numbers (columns). The third index is used to distinguish processing times and accumulative makespan values. The matrix is as informative as the Gantt Chart and yet offers additional advantages when considering the flow-shop problem, such as: 1. Provides an instructional tableau format which is organized, systematic, and directly amenable for hand or digital-computer calculations, 2. Depicts computational contingencies for accumulative makespan values (individual job due-dates as well as flow-shop makespan), 3. Depicts machine and job dominances, 4. Allows for sensitivity analysis {effects of processing times upon accumulative makespan values), 5. Identifies critical-processing times, 6. Reveals where external improvements would be cost effective, 7. Representation is easily modified for job permutations, 8. Representation is not limited to small flow-shops (low number of jobs and/or machines), 9. Allows for additional insight when investigating heuristics, and 10. Can be used as an instructional- , managerial- , and/or a research- tool for analyzing flow-shop attributes. The tableau allows a macro-sensitivity analysis of the entire flow-shop. Specifically, the maximum increase in various processing times, without increasing the flow-shop make span, can be determined. This analysis utilizes graphical representations (segments and nodes) in matrix (tableau). Graphical representation is a convenient means for preserving the history of how each accumulative makespan value was mathematically generated. Concepts such as: partial-paths and critical-paths in conjunction with regions-of-influence are discussed in order to determine the interrelationship between the accumulative makespan values and the processing times, for a specific job sequence."],"dc:description.degree":["M. S."],"dc:format.mimetype":["application/pdf"],"dc:identifier.uri":["http://hdl.handle.net/10919/114608"],"dc:language.iso":["en"],"dc:publisher":["Virginia Polytechnic Institute and State University"],"dc:rights":["In Copyright"],"dc:rights.uri":["http://rightsstatements.org/vocab/InC/1.0/"],"dc:title":["An analysis tableau and algorithm for flow-shop makespan minimization"],"dc:type":["Thesis"],"dc:type.dcmitype":["Text"],"thesis:degree_discipline":["Industrial Engineering and Operations Research"],"thesis:degree_level":["masters"],"thesis:degree_name":["M. S."],"thesis:institution_name":["Virginia Polytechnic Institute and State University"]},"updated_at":"2026-07-22T22:19:04Z"}