Online citations, reference lists, and bibliographies.
← Back to Search

Two-machine Flowshop Scheduling With A Secondary Criterion

V. T'kindt, J. Gupta, J. Billaut
Published 2003 · Computer Science, Mathematics

Save to my Library
Download PDF
Analyze on Scholarcy Visualize in Litmaps
Share
Reduce the time it takes to create your bibliography by a factor of 10 by using the world’s favourite reference manager
Time to take this seriously.
Get Citationsy
This paper develops mathematical programming formulations, a branch-and-bound algorithm, and a heuristic algorithm for solving the two-machine flowshop scheduling problem with the objective of minimizing total completion time, subject to the constraint that the makespan is minimum. The proposed branch-and-bound algorithm uses several lower bounding schemes, which are based on problem relaxations. Several dominance conditions are used in the algorithm to limit the size of the search tree. Results of extensive computational tests show that the proposed branch-and-bound algorithm is effective in solving problems with up to 35 jobs. For problems containing larger number of jobs, the proposed heuristic algorithm, which is also used as an upper bound in the proposed branch-and-bound algorithm, is quite effective in finding an optimal or near-optimal schedule.
This paper references
10.1002/NAV.3800010110
Optimal two- and three-stage production schedules with setup times included
S. Johnson (1954)
10.1287/moor.1.2.117
The Complexity of Flowshop and Jobshop Scheduling
M. Garey (1976)
10.1057/JORS.1989.58
Alternative Formulations of a Flow-shop Scheduling Problem
J. M. Wilson (1989)
10.1007/BF03500931
Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation
S. Velde (1991)
10.1057/JORS.1992.126
Two-Stage Flowshop Scheduling Problem with Bicriteria
C. Rajendran (1992)
10.1057/JORS.1995.102
A Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem
Amit Nagar (1995)
10.1016/0377-2217(95)00351-7
The two-machine total completion time flow shop problem
F. Croce (1996)
10.1016/0377-2217(95)00275-8
Genetic algorithms for the two-stage bicriteria flowshop problem
Venkata Ranga Neppalli (1996)
10.1007/978-1-4419-7997-1
Handbook of Combinatorial Optimization
D. Du (1998)
10.1080/095372899233217
Designing a tabu search algorithm for the two-stage flow shop problem with secondary criterion
陳春龍 (1999)
10.1109/ICSMC.1999.816596
Some guidelines to solve multicriteria scheduling problems
V. T'kindt (1999)
10.1051/ro:2001109
Multicriteria scheduling problems: a survey
V. T'kindt (2001)
10.1016/S0925-5273(00)00039-6
Minimizing total flow time in a two-machine flowshop problem with minimum makespan
Jatinder N. D. Gupta (2001)
10.1016/S0305-0548(00)00061-7
Local search heuristics for two-stage flow shop problems with secondary criterion
Jatinder N. D. Gupta (2002)
10.1016/S0377-2217(01)00374-5
An improved branch-and-bound algorithm for the two machine total completion time flow shop problem
F. Croce (2002)



This paper is referenced by
10.1016/j.eswa.2020.113556
A comprehensive review of Branch-and-Bound algorithms: Guidelines and directions for further research on the flowshop scheduling problem
C. P. Tomazella (2020)
10.29121/granthaalayah.v7.i1.2019.1036
JOB SHOP SCHEDULING CONSIDERING MAKESPAN, PENALTIES OF MACHINE IDLING, AND JOB OUT OF TIME
Jaber S. Alzahrani (2019)
10.18081/2226-3284/018-4/36-47
On the Two Machine Permutation Flowshop Scheduling Problems Using Variable Neighborhood Search Algorithms
T. A. Razaq (2018)
10.1007/s10479-018-2775-5
Non-permutation flowshop scheduling problem with minimal and maximal time lags: theoretical study and heuristic
Emna Dhouib (2018)
10.5755/J01.MECH.23.4.15053
AN EFFECTIVE GENETIC ALGORITHM FOR FLOW SHOP SCHEDULING PROBLEMS TO MINIMIZE MAKESPAN
Jeen Robert R.B (2017)
Machine Tool Scheduling Problem for Reconfigurable Manufacturing System ( RMS ) 1
A. Bhargav (2017)
10.1016/J.MATPR.2017.07.071
Study of Production Scheduling Problem for Reconfigurable Manufacturing System (RMS)
A. Bhargav (2017)
10.4028/www.scientific.net/JERA.26.142
Scheduling Problems of Flexible Manufacturing Systems: Review, Classification and Opportunities
Ghita Lebbar (2016)
10.1016/j.ejor.2015.05.057
Practical solutions for a dock assignment problem with trailer transportation
L. Berghman (2015)
10.1007/978-981-13-1799-6_20
A Multiobjective Genetic Algorithm for Hybrid Flow Shop of a Harddisk Drive's Manufacturer
Wanida Laoraksakiat (2015)
10.17485/IJST/2015/V8I11/71761
Using Gravitational Search Algorithm for in Advance Reservation of Resources in Solving the Scheduling Problem of Works in Workflow Workshop Environment
Hamid Tavakkolai (2015)
10.1504/IJFCM.2014.064225
Multi-objective fuzzy job shop scheduling
M. Singh (2014)
10.1016/j.ejor.2013.09.033
Bicriteria hierarchical optimization of two-machine flow shop scheduling problem with time-dependent deteriorating jobs
Mingbao Cheng (2014)
10.1016/J.OMEGA.2013.07.004
Multi-objective permutation flow shop scheduling problem: Literature review, classification and current trends
M. M. Yenisey (2014)
10.1002/9781118731598.CH4
A Comparison of Local Search Metaheuristics for a Hierarchical Flow Shop Optimization Problem with Time Lags
Emna Dhouib (2013)
10.1111/j.1475-3995.2012.00876.x
Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints
Emna Dhouib (2013)
10.1007/978-1-4614-5152-5_2
The Two-Machine Flow Shop
H. Emmons (2013)
10.1109/WCICA.2012.6358274
A hybrid genetic algorithm/fuzzy dynamic programming approach to two-machine flowshop problems
Hong Zhang (2012)
10.1007/978-3-642-29828-8_5
Complete Characterization of Near-Optimal Sequences for the Two-Machine Flow Shop Scheduling Problem
J. Billaut (2012)
MACHINE SCHEDULING MODELS FOR WAREHOUSING DOCKING OPERATIONS
Lotte Berghman (2012)
A Multi-objective Immune System for a New Bi-objective Permutation Flowshop Problem with Sequence-dependent Setup Times
Tavakkoli-Moghaddam (2012)
10.1007/s10845-009-0370-y
Ant colony optimization algorithm for a Bi-criteria 2-stage hybrid flowshop scheduling problem
E. L. Solano-Charris (2011)
10.4018/978-1-61692-020-3.CH014
Multicriteria Flow-Shop Scheduling Problem
E. Mokotoff (2011)
10.1007/S00170-010-3094-4
Multi-objective optimization algorithms for flow shop scheduling problem: a review and prospects
Yi Sun (2011)
ON JOB-SHOP AND FLOW-SHOP SCHEDULING USING MULTI CRITERIA DECISION MAKING
S. Parveen (2011)
10.3934/JIMO.2011.7.253
Algorithms for bicriteria minimization in the permutation flow shop scheduling problem
E. Mokotoff (2011)
10.1080/00207543.2010.523724
A multi-objective flow shop scheduling with resource-dependent processing times: trade-off between makespan and cost of resources
H. Mokhtari (2011)
10.2139/ssrn.1974492
Practical Solutions for a Dock Assignment Problem with Trailer Transportation
L. Berghman (2011)
10.1016/j.cor.2009.03.021
Flexible solutions in disjunctive scheduling: General formulation and study of the flow-shop case
M. Aloulou (2010)
10.3329/JME.V41I2.7508
REVIEW ON JOB-SHOP AND FLOW-SHOP SCHEDULING USING
S. Parveen (2010)
10.1016/j.eswa.2009.06.105
A multi-objective ant colony system algorithm for flow shop scheduling problem
Betul Yagmahan (2010)
10.1007/978-3-642-02836-6_4
Multi-objective Simulated Annealing for Permutation Flow Shop Problems
E. Mokotoff (2009)
See more
Semantic Scholar Logo Some data provided by SemanticScholar