Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Chinese Journal of Mechanical Engineering
Erschienen in: Chinese Journal of Mechanical Engineering 3/2017

01.05.2017 | Original Article

Effective Iterated Greedy Algorithm for Flow-Shop Scheduling Problems with Time lags

verfasst von: Ning ZHAO, Song YE, Kaidian LI, Siyu CHEN

Erschienen in: Chinese Journal of Mechanical Engineering | Ausgabe 3/2017

Einloggen, um Zugang zu erhalten

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Flow shop scheduling problem with time lags is a practical scheduling problem and attracts many studies. Permutation problem(PFSP with time lags) is concentrated but non-permutation problem(non-PFSP with time lags) seems to be neglected. With the aim to minimize the makespan and satisfy time lag constraints, efficient algorithms corresponding to PFSP and non-PFSP problems are proposed, which consist of iterated greedy algorithm for permutation(IGTLP) and iterated greedy algorithm for non-permutation (IGTLNP). The proposed algorithms are verified using well-known simple and complex instances of permutation and non-permutation problems with various time lag ranges. The permutation results indicate that the proposed IGTLP can reach near optimal solution within nearly 11% computational time of traditional GA approach. The non-permutation results indicate that the proposed IG can reach nearly same solution within less than 1% computational time compared with traditional GA approach. The proposed research combines PFSP and non-PFSP together with minimal and maximal time lag consideration, which provides an interesting viewpoint for industrial implementation.
Vorheriger Artikel Tribological Testing of Hemispherical Titanium Pin Lubricated by Novel Palm Oil: Evaluating Anti-Wear and Anti-Friction Properties
Nächster Artikel Real-time OHT Dispatching Mechanism for the Interbay Automated Material Handling System with Shortcuts and Bypasses
Literatur
1.
HODSON A, MUHLEMANN A P, PRICE D H R. A microcomputer based solution to a practical scheduling problem[J]. Journal of the Operational Research Society, 1985, 36(10): 903–914.
2.
FONDREVELLE J, OULAMARA A, PORTMANN M C. Permutation flowshop scheduling problems with maximal and minimal time lags[J]. Computers & Operations Research, 2006, 33: 1540–1556.
3.
SOUKHAL A, OULAMARA A, MARTINEAU P. Complexity of flow shops scheduling problems with transportation constraints[J]. European Journal of Operational Research, 2005, 161(1): 32–41.
4.
CHU C, PROTH J. Single machine scheduling with chain structured precedence constraints and separation time windows[J]. IEEE Transactions on Robotics and Automation, Dec, 1996, 12(6): 835–843.
5.
KIM Y D, LIM H G, PARK M-W. Search heuristics for a flowshop scheduling problem in a printed circuit board assembly process[J]. European Journal of Operational Research, 1996, 91(1): 124–143.
6.
MANIER M A, BLOCH, C. A classification of hoist scheduling problems[J]. International Journal of Flexible Manufacturing Systems, 2003, 15(1): 37–55.
7.
YANG D L, CHERN M S. A two-machine flowshop sequencing problem with limited waiting time constraints[J]. Computers & Industrial Engineering, 1995, 28(1): 63–70.
8.
TANG Dunbing, DAI Min. Energy-efficient approach to minimizing the energy consumption in an extended Job-shop scheduling problem[J]. Chinese Journal of Mechanical Engineering, 2015, 28(5): 1048–1055.
9.
NAWAZ M, ENSCORE J E E, HAM I. A heuristic algorithm for the n-job, m-machine sequencing problem[J]. Management Science 1983 16/B: 630–637.
10.
HAMDI I, LOUKIL T. Minimizing total tardiness in the permutation flowshop scheduling problem with minimal and maximal time lags[J]. Operational Research, 2015, 15(1): 95–114.
11.
NIKBAKHSH J P, MOHAMMAD F M, MOHAMMAD K. An immune algorithm for hybrid flow shop scheduling problem with time lags and sequence-dependent setup times[J]. The International Journal of Advanced Manufacturing Technology, 2012, 63(1–4): 337–348.
12.
DHOUIB E, TEGHEM J, LOUKIL T. Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints[J]. International Transactions in Operational Research, 2013, 20(2): 213–232.
13.
SHEIKH S. Multi-objective flexible flow lines with due window, time lag, and job rejection [J]. The International Journal of Advanced Manufacturing Technology, 2013, 64(9–12): 1423–1433.
14.
WANG B L, WANG H F, LI T K. Gene exchange operators of partheno-genetic algorithm for permutation flowshop scheduling with maximum and minimum time lag constraints[C]//2015 International Conference on Material Engineering and Information Technology Applications(MEITA), Guilin, Aug 30–31, 2015: 596–600.
15.
AMROUCHE K, BOUDHAR M. Two machines flow shop with reentrance and exact time lag[J]. RAIRO-Operations Research, 2016, 50(2): 223–232.
16.
SANG H, GAO L, PAN Q K. Discrete artificial bee colony algorithm for lot-streaming flowshop with total flowtime minimization[J]. Chinese Journal of Mechanical Engineering, 2012, 25(5): 990-1000.
17.
ZHAO N, CHEN S Y, DU Y H. Emergency local searching approach for Job shop scheduling[J]. Chinese Journal of Mechanical Engineering, 2013, 26(5): 918–927.
18.
CAUMOND A, LACOMME P, TCHERNEV N. A memetic algorithm for the job-shop with time lags[J]. Computers & Operations Research, 2008, 35(7): 2331–2356.
19.
ARTIGUES C, HUGUET M J, LOPEZ P. Generalized disjunctive constraint propagation for solving the job shop problem with time lags[J]. Engineering Applications of Artificial Intelligence, 2011, 24(2): 220–231.
20.
GONZALEZ M A, ODDI A, RASCONI R, et al. Scatter search with path relinking for the job shop with time lags and setup times[J]. Computers & Operations Research, 2015, 60: 37–54.
21.
AFSAR H M, LACOMME P, REN L, et al. Resolution of a Job-Shop problem with transportation constraints: a master/slave approach[J]. IFAC-PapersOnLine, 2016, 49(12): 898–903.
22.
JOHNSON S M. Optimal two-and three-stage production schedules with setup times included[J]. Naval Research Logistics Quarterly, 1954, 1(1): 61–68.
23.
RUIZ R, STUTZLE T. A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem[J]. European Journal of Operational Research, 2007, 177: 2033–2049.
24.
PAN Q K, WANG L, ZHAO B H. An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion[J]. The International Journal of Advanced Manufacturing Technology, 2008 38 (7–8): 778–786.
25.
DING J Y, SONG S J, ZHANG R et al. Accelerated methods for total tardiness minimization in no-wait flowshops[J]. International Journal of Production Research, 2015, 53(4): 1002–1018.
26.
YING K C. Solving non-permutation flowshop scheduling problems by an effective iterated greedy heuristic[J]. The International Journal of Advanced Manufacturing Technology, 2008, 38(3-4): 348–354.
27.
HARRISON R, VERA D, AHMAD B. Engineering the smart factory[J]. Chinese Journal of Mechanical Engineering, 2016, 29(6): 1046–1051.
28.
CHEN D N, ZHANG R X, YAO C Y, et al. Dynamic topology multi force particle swarm optimization algorithm and its application[J]. Chinese journal of mechanical engineering, 2016, 29(1): 124–135.
29.
WANG Y Y, MOU S D, WU Y H. Storage assignment optimization in a multi-tier shuttle warehousing system[J]. Chinese journal of mechanical engineering, 2016, 29(2): 421–429.
30.
BUCKER P, KNUST S, CHENG T C E, et al. Complexity results for flow-shop and open-shop scheduling problems with transportation delays[J]. Annals of Operations Research, 2004, 129(1–4): 81–106.
31.
DELL’AMICO M. Shop problems with two machines and time lags[J]. Operations Research, 1996, 44(5): 777–787.
32.
MITTEN L G. Sequencing n jobs on two machines with arbitrary time lags[J]. Management Science, 1959, 5(3): 293–298.
33.
OSMAN I H, POTTS C N. Simulated annealing for permutation flow-shop scheduling[J]. Omega, 1989, 17(6): 551–557.
34.
HAMDI I, LOUKIL T. Minimizing the makespan in the permutation flowshop problem with maximal and minimal time lags[C]//2011 International Conference on Communications, Computing and Control Applications(CCCA), Hammamet, March 3–5, 2011: 1–6.
Metadaten
Titel
Effective Iterated Greedy Algorithm for Flow-Shop Scheduling Problems with Time lags
verfasst von
Ning ZHAO
Song YE
Kaidian LI
Siyu CHEN
Publikationsdatum
01.05.2017
Verlag
Chinese Mechanical Engineering Society
Erschienen in
Chinese Journal of Mechanical Engineering / Ausgabe 3/2017
Print ISSN: 1000-9345
Elektronische ISSN: 2192-8258
DOI
https://doi.org/10.1007/s10033-017-0108-2

Weitere Artikel der Ausgabe 3/2017

Chinese Journal of Mechanical Engineering 3/2017 Zur Ausgabe

Original Article

Shape Error Analysis of Functional Surface Based on Isogeometrical Approach

Original Article

Tribological Testing of Hemispherical Titanium Pin Lubricated by Novel Palm Oil: Evaluating Anti-Wear and Anti-Friction Properties

Editorial

Special Issue on Electromechanical Coupling Design for Electronic Equipment

Original Article

Design Property Network-Based Change Propagation Prediction Approach for Mechanical Product Development

Review article

Pulsed Eddy Current Non-destructive Testing and Evaluation: A Review

Review Article

Machining the Integral Impeller and Blisk of Aero-Engines: A Review of Surface Finishing and Strengthening Technologies

Premium Partner

    Marktübersichten

    Die im Laufe eines Jahres in der „adhäsion“ veröffentlichten Marktübersichten helfen Anwendern verschiedenster Branchen, sich einen gezielten Überblick über Lieferantenangebote zu verschaffen. 

    Zur Marktübersicht
    Bildnachweise