Branch-and-bound algorithms for scheduling in permutation flowshops to minimize the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime, weighted tardiness and weighted earliness of jobs

N Madhushini (), C Rajendran () and Y Deepa
Additional contact information
N Madhushini: Indian Institute of Technology Madras
C Rajendran: Indian Institute of Technology Madras
Y Deepa: Indian Institute of Technology Madras

Journal of the Operational Research Society, 2009, vol. 60, issue 7, 991-1004

Abstract: Abstract The problem of scheduling in permutation flowshops is considered in this paper with the objectives of minimizing the sum of weighted flowtime/sum of weighted tardiness/sum of weighted flowtime and weighted tardiness/sum of weighted flowtime, weighted tardiness and weighted earliness of jobs, with each objective considered separately. Lower bounds on the given objective (corresponding to a node generated in the scheduling tree) are developed by solving an assignment problem. Branch-and-bound algorithms are developed to obtain the best permutation sequence in each case. Our algorithm incorporates a job-based lower bound (integrated with machine-based bounds) with respect to the weighted flowtime/weighted tardiness/weighted flowtime and weighted tardiness, and a machine-based lower bound with respect to the weighted earliness of jobs. The proposed algorithms are evaluated by solving many randomly generated problems of different problem sizes. The results of an extensive computational investigation for various problem sizes are presented. In addition, one of the proposed branch-and-bound algorithms is compared with a related existing branch-and-bound algorithm.

Keywords: flowshop scheduling; assignment problem; weighted flowtime; weighted tardiness; weighted earliness; branch-and-bound algorithms (search for similar items in EconPapers)
Date: 2009
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1057/palgrave.jors.2602642 Abstract (text/html)
Access to full text is restricted to subscribers.

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:pal:jorsoc:v:60:y:2009:i:7:d:10.1057_palgrave.jors.2602642

Ordering information: This journal article can be ordered from
http://www.springer. ... search/journal/41274

DOI: 10.1057/palgrave.jors.2602642

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald and Jonathan Crook

More articles in Journal of the Operational Research Society from Palgrave Macmillan, The OR Society
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().