A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times
International Journal of Production EconomicsPublished 17 February 2005
Djamel Nait Tahar, Farouk Yalaoui, Chengbin Chu, Lionel Amodeo
Citations107
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.
TL;DR
A heuristic algorithm improving an existing one, using a linear programming modeling with setup times and job splitting considerations is suggested, which is tested on over 6000 instances with different size by comparing it with a lower bound.
Abstract
International audience
Keywords
Computer ScienceEngineering
Operations ResearchAn Algorithm for the Traveling Salesman Problem
1,049 Citations1963John D. C. Little, Katta G. Murty +2 more
A “branch and bound” algorithm is presented for solving the traveling salesman problem, where the set of all tours feasible solutions is broken up into increasingly small subsets by a procedure called branching.
OmegaA review of scheduling research involving setup considerations
911 Citations1999Ali Allahverdi, Jatinder N.D. Gupta +1 more
A comprehensive review of the literature on scheduling problems involving setup times (costs) classifies scheduling problems into batch and non-batch, sequence-independent and sequence-dependent setup, and categorizes the literature according to the shop environments of single machine, parallel machines, flowshops, and job shops.
Operations ResearchParallel Sequencing and Assembly Line Problems
895 Citations1961T. C. Hu
This paper deals with a new sequencing problem in which n jobs with ordering restrictions have to be done by men of equal ability, and how to arrange a schedule that requires the minimum number of men to complete all jobs within a prescribed time T.
Management ScienceScheduling with Deadlines and Loss Functions
846 Citations1959Robert McNaughton
The problem of this paper is that of scheduling several one-stage tasks on several processors, which are capable of handling the tasks with varying degrees of efficiency, to minimize the total loss, which is a sum of losses associated with the individual tasks.
Operations ResearchSequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
551 Citations1964Paul C. Gilmore, Ralph E. Gomory
European Journal of Operational ResearchA state-of-the-art review of parallel-machine scheduling research
507 Citations1990T.C.E. Cheng, C.C.S. Sin
The major research results in deterministic parallel-machine scheduling theory will pass a survey and it is revealed that there exist a lot of potential areas worthy of further research.
SIAM Journal on ComputingApproximation Algorithms for Some Routing Problems
419 Citations1978Greg N. Frederickson, Matthew S. Hecht +1 more
Several polynomial time approximation algorithms for some NP-complete routing problems are presented, and the worst-case ratios of the cost of the obtained route to that of an optimal are determined.
Discrete Applied MathematicsAnalysis of a linear programming heuristic for scheduling unrelated parallel machines
166 Citations1985Chris N. Potts
A heuristic method which uses linear programming to form a partial schedule leaving at most m−1 jobs unscheduled and which has a (best possible) worst-case performance ratio of 2 and a computational requirement which is polynomial in n although it is exponential in m.
International Journal of Production ResearchImpact of sequence-dependent setup time on job shop scheduling performance
140 Citations1994S. C. KIM, Paul M. Bobrowski
Operations ResearchPathology of Traveling-Salesman Subtour-Elimination Algorithms
128 Citations1971Mandell Bellmore, John C. Malone
An underlying theory for the traveling-salesman problem is developed, pathological performance of some existing techniques are predicted, and two algorithms are presented, based upon the theory, with predictable polynomial growth in expected computation time and resistence to pathological problems.
ACM Transactions on Mathematical SoftwareExact solution of large-scale, asymmetric traveling salesman problems
109 Citations1995G. Carpaneto, Mauro Dell’Amico +1 more
A lowest-first, branch-and-bound algorithm for the Asymmetric Traveling Salesman Problem based on the Assignment Problem relaxation and on a tour elimination branching scheme that solves real-world problems with up to 443 movements in less than 6 seconds.
ACM Transactions on Mathematical SoftwareAlgorithm 548: Solution of the Assignment Problem [H]
103 Citations1980G. Carpaneto, Paolo Toth
R H U first ( s ) nex t (s) last ( s) as the row ass igned to c o l u m n y ( j -1 ) as the label o f c o L R , = 0, row i is un labe led (i = 1 , . . . , n);
Discrete Applied MathematicsParallel machine scheduling with splitting jobs
96 Citations2000Wenxun Xing, Jiawei Zhang
A heuristic ML and its worst- case analysis are shown for P / split / C max with independent job setup times and the worst-case performance ratio of ML is within 7 4 −1/m (m⩾2) .
IIE TransactionsAn efficient heuristic approach for parallel machine scheduling with job splitting and sequence-dependent setup times
85 Citations2003Farouk Yalaoui, Chengbin Chu
A heuristic to solve a real-life identical parallel machine scheduling problem with sequence-dependent setup times and job splitting to minimize makespan and develops a lower bound and evaluates the performances of the heuristic on a large number of randomly generated instances.
International Journal of Production ResearchScheduling sequence-dependent jobs on identical parallel machines to minimize completion time criteria
82 Citations1993Alain Guinet
International Journal of Production ResearchScheduling in a two-stage manufacturing process
70 Citations1984SEETUARMA L. NARASTMHAN, SHRTKANT S. PANWALKAR
An heuristic solution procedure known as the CMD rule is presented for this multi-product, multistage, continuous flow problem and is designed to minimize the sum of idle time of machines and in-process waiting at the second stage.
European Journal of Operational ResearchA hybrid two-stage flowshop with part family, batch production, major and minor set-ups
64 Citations1997Shanling Li
The computational results show that the Backward Heuristic, in general, is superior to the Forward Heuristic and the sequence rules developed in this paper also perform better than the traditional sequence rules such as SPT and LPT.
Production Planning & ControlModels and algorithms for a two-stage production process
54 Citations1990Hanif D. Sherali, Subhash C. Sarin +1 more
Operations ResearchA Production Scheduling Problem in the Glass-Container Industry
53 Citations1979R. J. Paul
This work examines the problem of scheduling parallel production lines in the glass-container industry with a resource constraint imposed by the furnace melting rate and concludes that a shortest processing time based dispatching rule probably provides the most efficient operating policy.
Decision SciencesA COMPARISON OF SEQUENCING RULES FOR A TWO‐STATE HYBRID FLOW SHOP
53 Citations1987Seetharama L. Narasimhan, Paul Mangiameli
This paper extends the rule presented by Narasimhan and Panwalker to include a general class of hybrid flow shops and demonstrates that the GCMD rule is better than the other rules in minimizing each of five chosen criteria.
OmegaScheduling jobs with uncertain setup times and sequence dependency
49 Citations1997Seung Chul Kim, Paul M. Bobrowski
Investigation of the impact of setup-time variation on sequencing decisions, with normally-distributed setup times, shows that setup- time variation has a negative impact on shop performance, but does not diminish the advantages of Setupconscious sequencing rules over conventional sequencing rules in dealing with setup times.
Annals of discrete mathematicsComputational Performance of Three Subtour Elimination Algorithms for Solving Asymmetric Traveling Salesman Problems
47 Citations1977T. H. C. Smith, V. Srinivasan +1 more
Three implicit enumeration algorithms for solving the asymmetric traveling salesman problem with subtour elimination using the assignment problem relaxation similar to the previous approaches by Eastman, Shapiro and Bellmore and Malone are developed and computationally test.
European Journal of Operational ResearchThe asymmetric traveling salesman problem with replenishment arcs
37 Citations2000Natashia Boland, Lloyd W. Clarke +1 more
A constrained asymmetric traveling salesman problem with knapsack-like constraints on subpaths of the tour with an exponential number of variables that correspond to feasible sub paths is considered and a branch- and-price-and-cut algorithm for solving it is presented.
International Journal of Operations & Production ManagementNew trends in parallel machine scheduling
30 Citations1997Kokin Lam, Wenxun Xing
Some new trends in parallel machine scheduling (PMS) are reviewed, including non‐regular objectives oriented by the JIT concept; pre‐emption with set‐up; capacitated machine scheduling; and relationships between PMS and vehicle routeing problems.
International Journal of Production EconomicsUsing metaheuristics for solving a production scheduling problem in a chemical firm. A case study
29 Citations1996Philippe Fortemps, Ch. Ost +3 more
The simulated annealing or tabu metaheuristics are applied to optimize the order of the jobs and some comparisons are made to analyse and compare the efficiency of the heuristics.
Information Processing LettersA heuristic algorithm for minimizing mean flow time with unit setups
28 Citations2001Svetlana A. Kravchenko, Frank Werner
A heuristic algorithm with an absolute error bounded by the product of the number of short jobs (with processing times less than m−1 ) and m−2 is given.
Academy of Management ReviewImpact of the Setup Variable on Capacity and Inventory Decisions
27 Citations1988Chan K. Hahn, Daniel J. Bragg +1 more
European Journal of Operational ResearchCluster based branching for the asymmetric traveling salesman problem
14 Citations1999Jens Lysgaard
A new branching scheme for the asymmetric traveling salesman problem (ATSP) based on clusters is presented, implemented in a branch and bound algorithm using a well-known additive bounding procedure.
HAL (Le Centre pour la Communication Scientifique Directe)Parallel machine scheduling with job splitting and setup times : A Heuristic Approach and Performance Analysis
1 Citations1999Farouk Yalaoui, Chengbin Chu