Scheduling Piecewise Linear Deteriorating Jobs to Minimize Makespan in a Two-Machine Flowshop

Abbasali Jafari-Nodoushan (), Hassan Khademi Zare (), M. M. Lotfi () and R. Tavakkoli-Moghaddam ()
Additional contact information
Abbasali Jafari-Nodoushan: Meybod University
Hassan Khademi Zare: Yazd University
M. M. Lotfi: Yazd University
R. Tavakkoli-Moghaddam: University of Tehran

SN Operations Research Forum, 2021, vol. 2, issue 4, 1-29

Abstract: Abstract A job processed later may consume more time in many realistic machine scheduling situations than the same job when processed earlier. This phenomenon is known as the deterioration of jobs. In this paper, two-machine flowshop scheduling problem under piecewise linear deteriorating jobs is investigated where the objective is to minimize the makespan. Deteriorating jobs may increase the makespan and it is important to obtain the optimal or near-optimal solution. Tab;At first, a Mixed Integer Non-Linear Programming (MINLP) model is presented for the problem and linearization of it is performed. After that, a branch and bound algorithm with dominance rules and lower bounds is established to solve the problem optimally. Several simple heuristics are also proposed to derive near-optimal solutions. The computational experiments are conducted through randomly generated examples to evaluate the performance of the proposed algorithms. The results demonstrate that the branch and bound algorithm can solve most medium-sized problems within a reasonable time. The heuristic algorithm is relatively accurate, with an average error percentage of less than 1.6%.

Keywords: Scheduling; Flowshop; Deteriorating jobs; Branch and bound; Heuristic (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s43069-021-00096-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:snopef:v:2:y:2021:i:4:d:10.1007_s43069-021-00096-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-021-00096-7

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().