Loading…

A Dynamic Programming Approach to Stochastic Assembly Line Balancing

Consider the problem of minimizing the required number of work stations on an assembly line for a given cycle time when the processing times are independent, normally distributed random variables. The assignment of tasks to stations is subject to precedence conditions, caused by technological constr...

Full description

Saved in:

Bibliographic Details
Published in:	Management science 1989-04, Vol.35 (4), p.459-471
Main Author:	Carraway, Robert L
Format:	Article
Language:	English
Subjects:	Algorithms Applied sciences Assembly lines Cost allocation Determinism Dynamic programming Exact sciences and technology Gaussian distributions line balancing Operational research and scientific management Operational research. Management science production production/scheduling Programming Random variables Recursion scheduling Scheduling, sequencing stochastic models Storage time Work stations
Citations:	Items that cite this one
Online Access:	Get full text
Tags:	Add Tag No Tags, Be the first to tag this record!

cited_by	cdi_FETCH-LOGICAL-c444t-3a18aed7526dd4601e2ad35e04f116143fc9bd38d4148fc522a629e650c8d60f3
cites
container_end_page	471
container_issue	4
container_start_page	459
container_title	Management science
container_volume	35
creator	Carraway, Robert L
description	Consider the problem of minimizing the required number of work stations on an assembly line for a given cycle time when the processing times are independent, normally distributed random variables. The assignment of tasks to stations is subject to precedence conditions, caused by technological constraints, and a lower bound on the probability of the work at any station being completed within the cycle time. We present two dynamic programming (DP) algorithms for this problem, each guaranteed to be optimal under a certain mild condition. Our general approach is based on the Held et al. (Held, M., R. M. Karp, R. Shareshian. 1963. Assembly-line-balancing-dynamic programming with precedence constraints. Oper. Res. 11 442–459.) formulation of the deterministic line balancing problem and thus represents a modification of previous work by Kao (Kao, E. P. C. 1976. A preference order dynamic program for stochastic assembly line balancing. Management Sci. 22 1097–1104.). Computational results indicate that both algorithms significantly outperform an alternative DP approach suggested by Henig (Henig, M. I. 1986. Extensions of the dynamic programming method in the deterministic and stochastic assembly-line balancing problems. Comput. Oper. Res. 13 443–449.).
doi_str_mv	10.1287/mnsc.35.4.459
format	article
fullrecord	<record><control><sourceid>jstor_proqu</sourceid><recordid>TN_cdi_proquest_journals_1297784575</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><jstor_id>2631892</jstor_id><sourcerecordid>2631892</sourcerecordid><originalsourceid>FETCH-LOGICAL-c444t-3a18aed7526dd4601e2ad35e04f116143fc9bd38d4148fc522a629e650c8d60f3</originalsourceid><addsrcrecordid>eNqF0E1v1DAQBuAIgcTScuTGIRKCXsji79jHpS0taCWQgLPlOs7GqzhO7Sxo_z0T0g-JC4fRHOax9c4UxSuM1pjI-kMYsl1TvmZrxtWTYoU5ERXnCD8tVggRXmGF1PPiRc57hFAta7EqLjblxXEwwdvyW4q7ZELww67cjGOKxnblFMvvU7SdyROQTc4u3PTHcusHV340vRks8NPiWWv67F7e9ZPi56fLH-fX1fbr1efzzbayjLGpogZL45oaYjUNEwg7YhrKHWItxgIz2lp101DZMMxkazkhRhDlBEdWNgK19KR4t_wL4W4PLk86-GxdDzFcPGRNhUJMKgnwzT9wHw9pgGwaE1XXkvGag6oWZVPMOblWj8kHk44aIz1fVM8X1ZRrpuGi4L8sPrnR2QfshxDTX_lLUwOamiMUVlJB81AMapw7V5rVWHdTgM_e3kU02Zq-TfMp82MCxbhUdF7l9eL2eYrpYU4ExVIRGL9fxn5oIUX-7wpnC-_8rvvtk9P374IB6B_lH97ntJc</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1297784575</pqid></control><display><type>article</type><title>A Dynamic Programming Approach to Stochastic Assembly Line Balancing</title><source>EBSCOhost Business Source Ultimate</source><source>International Bibliography of the Social Sciences (IBSS)</source><source>美国运筹学和管理学研究协会期刊（NSTL购买）</source><source>JSTOR Archival Journals and Primary Sources Collection</source><source>ABI/INFORM Global</source><creator>Carraway, Robert L</creator><creatorcontrib>Carraway, Robert L</creatorcontrib><description>Consider the problem of minimizing the required number of work stations on an assembly line for a given cycle time when the processing times are independent, normally distributed random variables. The assignment of tasks to stations is subject to precedence conditions, caused by technological constraints, and a lower bound on the probability of the work at any station being completed within the cycle time. We present two dynamic programming (DP) algorithms for this problem, each guaranteed to be optimal under a certain mild condition. Our general approach is based on the Held et al. (Held, M., R. M. Karp, R. Shareshian. 1963. Assembly-line-balancing-dynamic programming with precedence constraints. Oper. Res. 11 442–459.) formulation of the deterministic line balancing problem and thus represents a modification of previous work by Kao (Kao, E. P. C. 1976. A preference order dynamic program for stochastic assembly line balancing. Management Sci. 22 1097–1104.). Computational results indicate that both algorithms significantly outperform an alternative DP approach suggested by Henig (Henig, M. I. 1986. Extensions of the dynamic programming method in the deterministic and stochastic assembly-line balancing problems. Comput. Oper. Res. 13 443–449.).</description><identifier>ISSN: 0025-1909</identifier><identifier>EISSN: 1526-5501</identifier><identifier>DOI: 10.1287/mnsc.35.4.459</identifier><identifier>CODEN: MSCIAM</identifier><language>eng</language><publisher>Linthicum, MD: INFORMS</publisher><subject>Algorithms ; Applied sciences ; Assembly lines ; Cost allocation ; Determinism ; Dynamic programming ; Exact sciences and technology ; Gaussian distributions ; line balancing ; Operational research and scientific management ; Operational research. Management science ; production ; production/scheduling ; Programming ; Random variables ; Recursion ; scheduling ; Scheduling, sequencing ; stochastic models ; Storage time ; Work stations</subject><ispartof>Management science, 1989-04, Vol.35 (4), p.459-471</ispartof><rights>Copyright 1989 The Institute of Management Sciences</rights><rights>1991 INIST-CNRS</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c444t-3a18aed7526dd4601e2ad35e04f116143fc9bd38d4148fc522a629e650c8d60f3</citedby></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.jstor.org/stable/pdf/2631892$$EPDF$$P50$$Gjstor$$H</linktopdf><linktohtml>$$Uhttps://pubsonline.informs.org/doi/full/10.1287/mnsc.35.4.459$$EHTML$$P50$$Ginforms$$H</linktohtml><link.rule.ids>314,780,784,3692,27924,27925,33224,36051,36061,58238,58471,62616</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&idt=19458938$$DView record in Pascal Francis$$Hfree_for_read</backlink><backlink>$$Uhttp://econpapers.repec.org/article/inmormnsc/v_3a35_3ay_3a1989_3ai_3a4_3ap_3a459-471.htm$$DView record in RePEc$$Hfree_for_read</backlink></links><search><creatorcontrib>Carraway, Robert L</creatorcontrib><title>A Dynamic Programming Approach to Stochastic Assembly Line Balancing</title><title>Management science</title><description>Consider the problem of minimizing the required number of work stations on an assembly line for a given cycle time when the processing times are independent, normally distributed random variables. The assignment of tasks to stations is subject to precedence conditions, caused by technological constraints, and a lower bound on the probability of the work at any station being completed within the cycle time. We present two dynamic programming (DP) algorithms for this problem, each guaranteed to be optimal under a certain mild condition. Our general approach is based on the Held et al. (Held, M., R. M. Karp, R. Shareshian. 1963. Assembly-line-balancing-dynamic programming with precedence constraints. Oper. Res. 11 442–459.) formulation of the deterministic line balancing problem and thus represents a modification of previous work by Kao (Kao, E. P. C. 1976. A preference order dynamic program for stochastic assembly line balancing. Management Sci. 22 1097–1104.). Computational results indicate that both algorithms significantly outperform an alternative DP approach suggested by Henig (Henig, M. I. 1986. Extensions of the dynamic programming method in the deterministic and stochastic assembly-line balancing problems. Comput. Oper. Res. 13 443–449.).</description><subject>Algorithms</subject><subject>Applied sciences</subject><subject>Assembly lines</subject><subject>Cost allocation</subject><subject>Determinism</subject><subject>Dynamic programming</subject><subject>Exact sciences and technology</subject><subject>Gaussian distributions</subject><subject>line balancing</subject><subject>Operational research and scientific management</subject><subject>Operational research. Management science</subject><subject>production</subject><subject>production/scheduling</subject><subject>Programming</subject><subject>Random variables</subject><subject>Recursion</subject><subject>scheduling</subject><subject>Scheduling, sequencing</subject><subject>stochastic models</subject><subject>Storage time</subject><subject>Work stations</subject><issn>0025-1909</issn><issn>1526-5501</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1989</creationdate><recordtype>article</recordtype><sourceid>8BJ</sourceid><recordid>eNqF0E1v1DAQBuAIgcTScuTGIRKCXsji79jHpS0taCWQgLPlOs7GqzhO7Sxo_z0T0g-JC4fRHOax9c4UxSuM1pjI-kMYsl1TvmZrxtWTYoU5ERXnCD8tVggRXmGF1PPiRc57hFAta7EqLjblxXEwwdvyW4q7ZELww67cjGOKxnblFMvvU7SdyROQTc4u3PTHcusHV340vRks8NPiWWv67F7e9ZPi56fLH-fX1fbr1efzzbayjLGpogZL45oaYjUNEwg7YhrKHWItxgIz2lp101DZMMxkazkhRhDlBEdWNgK19KR4t_wL4W4PLk86-GxdDzFcPGRNhUJMKgnwzT9wHw9pgGwaE1XXkvGag6oWZVPMOblWj8kHk44aIz1fVM8X1ZRrpuGi4L8sPrnR2QfshxDTX_lLUwOamiMUVlJB81AMapw7V5rVWHdTgM_e3kU02Zq-TfMp82MCxbhUdF7l9eL2eYrpYU4ExVIRGL9fxn5oIUX-7wpnC-_8rvvtk9P374IB6B_lH97ntJc</recordid><startdate>19890401</startdate><enddate>19890401</enddate><creator>Carraway, Robert L</creator><general>INFORMS</general><general>Institute of Management Sciences</general><general>Institute for Operations Research and the Management Sciences</general><scope>IQODW</scope><scope>DKI</scope><scope>X2L</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>K30</scope><scope>PAAUG</scope><scope>PAWHS</scope><scope>PAWZZ</scope><scope>PAXOH</scope><scope>PBHAV</scope><scope>PBQSW</scope><scope>PBYQZ</scope><scope>PCIWU</scope><scope>PCMID</scope><scope>PCZJX</scope><scope>PDGRG</scope><scope>PDWWI</scope><scope>PETMR</scope><scope>PFVGT</scope><scope>PGXDX</scope><scope>PIHIL</scope><scope>PISVA</scope><scope>PJCTQ</scope><scope>PJTMS</scope><scope>PLCHJ</scope><scope>PMHAD</scope><scope>PNQDJ</scope><scope>POUND</scope><scope>PPLAD</scope><scope>PQAPC</scope><scope>PQCAN</scope><scope>PQCMW</scope><scope>PQEME</scope><scope>PQHKH</scope><scope>PQMID</scope><scope>PQNCT</scope><scope>PQNET</scope><scope>PQSCT</scope><scope>PQSET</scope><scope>PSVJG</scope><scope>PVMQY</scope><scope>PZGFC</scope><scope>SAAPM</scope><scope>8BJ</scope><scope>FQK</scope><scope>JBE</scope></search><sort><creationdate>19890401</creationdate><title>A Dynamic Programming Approach to Stochastic Assembly Line Balancing</title><author>Carraway, Robert L</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c444t-3a18aed7526dd4601e2ad35e04f116143fc9bd38d4148fc522a629e650c8d60f3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1989</creationdate><topic>Algorithms</topic><topic>Applied sciences</topic><topic>Assembly lines</topic><topic>Cost allocation</topic><topic>Determinism</topic><topic>Dynamic programming</topic><topic>Exact sciences and technology</topic><topic>Gaussian distributions</topic><topic>line balancing</topic><topic>Operational research and scientific management</topic><topic>Operational research. Management science</topic><topic>production</topic><topic>production/scheduling</topic><topic>Programming</topic><topic>Random variables</topic><topic>Recursion</topic><topic>scheduling</topic><topic>Scheduling, sequencing</topic><topic>stochastic models</topic><topic>Storage time</topic><topic>Work stations</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Carraway, Robert L</creatorcontrib><collection>Pascal-Francis</collection><collection>RePEc IDEAS</collection><collection>RePEc</collection><collection>CrossRef</collection><collection>Periodicals Index Online</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - West</collection><collection>Primary Sources Access (Plan D) - International</collection><collection>Primary Sources Access & Build (Plan A) - MEA</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Midwest</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Northeast</collection><collection>Primary Sources Access (Plan D) - Southeast</collection><collection>Primary Sources Access (Plan D) - North Central</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Southeast</collection><collection>Primary Sources Access (Plan D) - South Central</collection><collection>Primary Sources Access & Build (Plan A) - UK / I</collection><collection>Primary Sources Access (Plan D) - Canada</collection><collection>Primary Sources Access (Plan D) - EMEALA</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - North Central</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - South Central</collection><collection>Primary Sources Access & Build (Plan A) - International</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - International</collection><collection>Primary Sources Access (Plan D) - West</collection><collection>Periodicals Index Online Segments 1-50</collection><collection>Primary Sources Access (Plan D) - APAC</collection><collection>Primary Sources Access (Plan D) - Midwest</collection><collection>Primary Sources Access (Plan D) - MEA</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - Canada</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - UK / I</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - EMEALA</collection><collection>Primary Sources Access & Build (Plan A) - APAC</collection><collection>Primary Sources Access & Build (Plan A) - Canada</collection><collection>Primary Sources Access & Build (Plan A) - West</collection><collection>Primary Sources Access & Build (Plan A) - EMEALA</collection><collection>Primary Sources Access (Plan D) - Northeast</collection><collection>Primary Sources Access & Build (Plan A) - Midwest</collection><collection>Primary Sources Access & Build (Plan A) - North Central</collection><collection>Primary Sources Access & Build (Plan A) - Northeast</collection><collection>Primary Sources Access & Build (Plan A) - South Central</collection><collection>Primary Sources Access & Build (Plan A) - Southeast</collection><collection>Primary Sources Access (Plan D) - UK / I</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - APAC</collection><collection>Primary Sources Access—Foundation Edition (Plan E) - MEA</collection><collection>Periodicals Index Online Segment 42</collection><collection>International Bibliography of the Social Sciences (IBSS)</collection><collection>International Bibliography of the Social Sciences</collection><collection>International Bibliography of the Social Sciences</collection><jtitle>Management science</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Carraway, Robert L</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A Dynamic Programming Approach to Stochastic Assembly Line Balancing</atitle><jtitle>Management science</jtitle><date>1989-04-01</date><risdate>1989</risdate><volume>35</volume><issue>4</issue><spage>459</spage><epage>471</epage><pages>459-471</pages><issn>0025-1909</issn><eissn>1526-5501</eissn><coden>MSCIAM</coden><abstract>Consider the problem of minimizing the required number of work stations on an assembly line for a given cycle time when the processing times are independent, normally distributed random variables. The assignment of tasks to stations is subject to precedence conditions, caused by technological constraints, and a lower bound on the probability of the work at any station being completed within the cycle time. We present two dynamic programming (DP) algorithms for this problem, each guaranteed to be optimal under a certain mild condition. Our general approach is based on the Held et al. (Held, M., R. M. Karp, R. Shareshian. 1963. Assembly-line-balancing-dynamic programming with precedence constraints. Oper. Res. 11 442–459.) formulation of the deterministic line balancing problem and thus represents a modification of previous work by Kao (Kao, E. P. C. 1976. A preference order dynamic program for stochastic assembly line balancing. Management Sci. 22 1097–1104.). Computational results indicate that both algorithms significantly outperform an alternative DP approach suggested by Henig (Henig, M. I. 1986. Extensions of the dynamic programming method in the deterministic and stochastic assembly-line balancing problems. Comput. Oper. Res. 13 443–449.).</abstract><cop>Linthicum, MD</cop><pub>INFORMS</pub><doi>10.1287/mnsc.35.4.459</doi><tpages>13</tpages></addata></record>
fulltext	fulltext
identifier	ISSN: 0025-1909
ispartof	Management science, 1989-04, Vol.35 (4), p.459-471
issn	0025-1909 1526-5501
language	eng
recordid	cdi_proquest_journals_1297784575
source	EBSCOhost Business Source Ultimate; International Bibliography of the Social Sciences (IBSS); 美国运筹学和管理学研究协会期刊（NSTL购买）; JSTOR Archival Journals and Primary Sources Collection; ABI/INFORM Global
subjects	Algorithms Applied sciences Assembly lines Cost allocation Determinism Dynamic programming Exact sciences and technology Gaussian distributions line balancing Operational research and scientific management Operational research. Management science production production/scheduling Programming Random variables Recursion scheduling Scheduling, sequencing stochastic models Storage time Work stations
title	A Dynamic Programming Approach to Stochastic Assembly Line Balancing
url	http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T01%3A49%3A04IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-jstor_proqu&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20Dynamic%20Programming%20Approach%20to%20Stochastic%20Assembly%20Line%20Balancing&rft.jtitle=Management%20science&rft.au=Carraway,%20Robert%20L&rft.date=1989-04-01&rft.volume=35&rft.issue=4&rft.spage=459&rft.epage=471&rft.pages=459-471&rft.issn=0025-1909&rft.eissn=1526-5501&rft.coden=MSCIAM&rft_id=info:doi/10.1287/mnsc.35.4.459&rft_dat=%3Cjstor_proqu%3E2631892%3C/jstor_proqu%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c444t-3a18aed7526dd4601e2ad35e04f116143fc9bd38d4148fc522a629e650c8d60f3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1297784575&rft_id=info:pmid/&rft_jstor_id=2631892&rfr_iscdi=true