Flow shop learning effect scheduling problem with release dates

Danyu Bai, Mengqian Tang, Zhi-Hai Zhang and Ernesto DR Santibanez-Gonzalez

Omega, 2018, vol. 78, issue C, 21-38

Abstract: In a real-world assembly environment, the components of a product arrive at a plant over time. Works-in-process are assembled into end-products by following an identical processing route. When a worker at a particular stage repeatedly handles similar tasks and gains the knowledge to execute a task efficiently, the processing time for later tasks is shortened significantly. This assembly process can be described as the flow shop learning effect scheduling problem with release dates, in which the learning effect is dependent on position. The objective is to minimize one of three different criteria, namely, makespan, total completion time and total quadratic completion time. This scheduling problem is formulated as a mixed integer programming (MIP) model. For small-scale problems, a branch and bound (B&B) algorithm with an efficient branching rule is proposed to obtain optimal solutions. The MIP model and the B&B algorithm provide key evidence for academic research. For large-scale problems, the asymptotic optimality of a class of shortest processing time available (SPTA)-based heuristics is proven in terms of probability limit. The convergence property indicates that an SPTA-based heuristic can serve as an optimal schedule under the industrial setting, where thousands of tasks are typically executed on a set of machines. Extensive numerical experiments demonstrate the effectiveness of the proposed algorithms.

Keywords: Flow shop scheduling; Learning effect; Branch and bound; Heuristic; Asymptotic analysis (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048316309434
Full text for ScienceDirect subscribers only

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:eee:jomega:v:78:y:2018:i:c:p:21-38

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2017.10.002

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().