Minimizing total flow time in a two-machine flowshop problem with minimum makespan
International Journal of Production EconomicsPublished 1 February 2001
Jatinder N.D. Gupta, Venkata Ranga Neppalli, Frank Werner
Citations66
SJR quartileQ1
SJR score2.83
SNIP2.67
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
Abstract
This paper considers the two-machine flowshop scheduling problem where it is desired to find a minimum total flow time schedule subject to the condition that the makespan of the schedule is minimum. Based on the analysis of the problem characteristics, several existing results are extended to develop two optimization algorithms for the problem. In view of the NP-hardness of the problem, two polynomially solvable cases are identified and solved. Further, several polynomial heuristic solution algorithms are developed and empirically evaluated as to their effectiveness in finding an optimal schedule for the problem.
Keywords
Engineering
Naval Research Logistics QuarterlyOptimal two‐ and three‐stage production schedules with setup times included
3,231 Citations1954S. M. Johnson
A simple decision rule is obtained in this paper for the optimal scheduling of the production so that the total elapsed time is a minimum.
OmegaA heuristic algorithm for the m-machine, n-job flow-shop sequencing problem
2,493 Citations1983Muhammad Nawaz, E. Emory Enscore +1 more
A simple algorithm is presented in this paper, which produces very good sequences in comparison with existing heuristics, and performs especially well on large flow-shop problems in both the static and dynamic sequencing environments.
Journal of the Operational Research SocietyLogistics of Production and Inventory
383 Citations1995Graham K. Rand
Part 1 Fundamentals: single-product single-location models, H.L. Lee and S. Nahmias; part 2 Production planning and scheduling: an overview of production planning, L.J. Thomas and J.O. Fine.
TU/e Research PortalSequencing and scheduling : algorithms and complexity
332 Citations1989Eugene L. Lawler, Jan Karel Lenstra +2 more
The final author version and the galley proof are versions of the publication after peer review that features the final layout of the paper including the volume, issue and page numbers.
European Journal of Operational ResearchMultiple and bicriteria scheduling: A literature survey
221 Citations1995Amit Nagar, Jorge Haddock +1 more
International Journal of Production EconomicsHeuristic algorithm for scheduling in a flowshop to minimize total flowtime
171 Citations1993Chandrasekharan Rajendran
Lecture notes in economics and mathematical systemsSequencing Research and the Industrial Scheduling Problem
162 Citations1973S. S. Panwalkar, Richard A. Dudek +1 more
Types of industrial scheduling problems were investigated by personal visits to plants and by questionnaires mailed to scheduling departments and results indicate that most of the present procedures in theoretical research cannot handle average industrial problems.
WORLD SCIENTIFIC eBooksComplexity in Numerical Optimization
161 Citations1993P. M. Pardalos
Average performance of self-dual interior point algorithm for linear programming and complexity results for a class of min-max problems with robust optimization applications.
A I I E TransactionsHeuristic Algorithms for Multistage Flowshop Scheduling Problem
120 Citations1972Jatinder N.D. Gupta
Three heuristic algorithms for seeking a quick and near optimal solution to the n-job M-machine flowshop scheduling problem where jobs are processed on all machines in the same order are described.
Naval Research Logistics (NRL)Multiobjective flow-shop scheduling
110 Citations1990Richard L. Daniels, Robert Chambers
European Journal of Operational ResearchGenetic algorithms for the two-stage bicriteria flowshop problem
102 Citations1996Venkata Ranga Neppalli, Chuen-Lung Chen +1 more
Two Genetic Algorithms (GA) based approaches are proposed to solve the two-stage bicriteria flow shop scheduling problem with the objective of minimizing the total flow time subject to obtaining the optimal makespan.
Journal of the Operational Research SocietyTwo-Stage Flowshop Scheduling Problem with Bicriteria
96 Citations1992Chandrasekharan Rajendran
The two-stage flowshop scheduling problem with the objective of minimizing total flowtime subject to obtaining the optimal makespan is discussed and a branch-and-bound algorithm and two heuristic algorithms have been developed.
Lecture notes in economics and mathematical systemsSymposium on the Theory of Scheduling and Its Applications
88 Citations1973Salah E. Elmaghraby
This chapter discusses Scheduling Problems by Applying Cost Operators to Assignment Models and some Extensions of Akers-Friedman Production Scheduling Problem.
Management ScienceFlowshop Sequencing Problem with Ordered Processing Time Matrices
86 Citations1975Marquard Smith, S. S. Panwalkar +1 more
Annals of Operations ResearchA combined branch-and-bound and genetic algorithm based approach for a flowshop scheduling problem
84 Citations1996Amit Nagar, Sunderesh S. Heragu +1 more
The results indicate that the combined approach and its modified versions are better than either of the pure strategies as well as the heuristic algorithm.
Discrete Applied MathematicsInsertion techniques for the heuristic solution of the job shop problem
84 Citations1995Frank Werner, Andreas Winkler
This paper deals with the heuristic solution of the classical job shop problem by applying insertion techniques combined with beam search to generate paths in a particular neighbourhood graph instead of investigating the neighbourhood completely.
Journal of the Operational Research SocietyA Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem
74 Citations1995Amit Nagar, Sunderesh S. Heragu +1 more
A branch-and-bound approach for solving a two-machine flow shop scheduling problem, in which the objective is to minimize a weighted combination of job flowtime and schedule makespan, can be used to guide other heuristic techniques in their search for optimal solutions for larger problems.
International Journal of Production ResearchAn ordered flow-shop sequencing problem with mean completion time criterion†
40 Citations1976S. S. Panwalkar, Abdul Waheed Khan
A I I E TransactionsOptimality Criteria for Flowshop Schedules
38 Citations1971Jatinder N.D. Gupta, Richard A. Dudek
Production Planning & ControlDesigning a tabu search algorithm for the two-stage flow shop problem with secondary criterion
36 Citations1999Jatinder N.D. Gupta
Mathematics and Computers in SimulationDeterministic scheduling in computing and manufacturing systems: a survey of models and algorithms
34 Citations1993Spyros G. Tzafestaş, Alekos Triantafyllakis
A unified formulation of deterministic scheduling models (problems) is provided on the basis of the three standard data fields, viz. the task set, the processor set, and the optimality criterion set.
RAIRO - Operations ResearchOn the application of insertion techniques for job shop problems with setup times
27 Citations1999Yuri N. Sotskov, Thomas Tautenhahn +1 more
Dans notre publication nous considerons differents problemes de « job shop scheduling » avec des temps de preparation avec d'autres algorithmes de priorite, plus precisement Item- and Batch-disponibilite.
A I I E TransactionsOptimal Scheduling in a Multistage Flowshop
23 Citations1972Jatinder N.D. Gupta
The combinatorial analysis for the flow shop scheduling problem is extended and an algorithm is proposed for the solution of the multistage flowshop scheduling problem, where the objective is to minimize a specified measure of total production cost and jobs have their associated start and stop lags.
Naval Research Logistics QuarterlyExtreme solutions of the two machine flow‐shop problem
5 Citations1981Włodzimierz Szwarc