Abstract
Scheduling is a major issue faced every day in manufacturing systems as well as in the service industry, so it is essential to develop effective and efficient advanced manufacturing and scheduling technologies and approaches. Also, it can be said that bi-criteria scheduling problems are classified in two general categories respecting the approach used to solve the problem. In one category, the aim is to determine a schedule that minimizes a convex combination of two objectives and in the other category is to find a good approximation of the set of efficient solutions. The aim of this paper is to determine a schedule for hybrid flowshop problem that minimizes a convex combination of the makespan and total tardiness. For the optimization problem, a meta-heuristic procedure is proposed based on the simulated annealing/local search (SA/LS) along with some basic improvement procedures. The performance of the proposed algorithm, SA/LS, is compared with a genetic algorithm which had been presented in the literature for hybrid flowshop with the objective of minimizing a convex combination of the makespan and the number of tardy jobs. Several computational tests are used to evaluate the effectiveness and efficiency of the proposed algorithm against the other algorithm provided in the literature. From the results obtained, it can be seen that the proposed algorithm in comparison with the other algorithm is more effective and efficient.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Daniels RL, Chambers RJ (1990) Multi-objective flow-shop scheduling. Nav Res Logist 37(6):981–995
Ishibuchi H, Murata T (1998) A multi-objective genetic local search algorithm and its application to flow shop scheduling. IEEE Transaction on Systems and Manufacturing Cybernetics 28(3):392–403
Sayin S, Karabati S (1999) A bi-criteria approach to the two-machine flow shop scheduling problem. Eur J Oper Res 113(2):435–449
Chakravarthy K, Rajendran C (1999) A heuristic for scheduling in a flow shop with the bi-criteria of makespan and maximum tardiness minimization. Production Planning and Control 10(7):707–714
Allahverdi A (2001) The tricriteria two-machine flow shop scheduling problem. International Transaction on Operational Research 8(4):403–425
Lee WC, Wu CC (2001) Minimizing the total flow time and the tardiness in a two-machine flow shop. Int J Syst Sci 32(3):365–373
Chang PC, Hsieh JC, Lin SG (2002) The development of gradual priority weighting approach for the multi-objective flowshop scheduling problem. Int J Prod Econ 79(3):171–183
Toktas B, Azizoglu M, Koksalan SK (2004) Two-machine flow shop scheduling with two criteria: maximum earliness and makespan. Eur J Oper Res 157(2):286–295
Ponnambalam SG, Jagannathan H, Kataria M, Gadicherla A (2004) A TSP-GA multi-objective algorithm for flow shop scheduling. Int J Adv Manuf Technol 23(11–12):909–915
Ravindran D, Noorul Haq A, Selvakuar SJ, Sivaraman R (2005) Flow shop scheduling with multiple objective of minimizing makespan and total flow time. Int J Adv Manuf Technol 25(9–10):1007–1012
Loukil T, Teghem J, Tuyttens D (2005) Solving multi-objective production scheduling problems using metaheuristics. Eur J Oper Res 161(1):42–61
Rahimi-Vahed AR, Mirghorbani SM, Rabbani M (2007) A new particle swarm algorithm for a multi-objective mixed-model assembly line sequencing problem. Soft Computing 11(10):997–1012
Jungwattanakit J, Reodecha M, Chaovalitwongse P, Werner F (2007) Algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria. Int J Adv Manuf Technol 37(3–4):354–370
Allahverdi A, Ng CT, Cheng TCE, Kovalyov MY (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187(3):985–1032
Kurz ME, Askin RG (2003) Scheduling flexible flow lines with sequence-dependent setup times. Eur J Oper Res 159(1):66–82
Kirkpatrik S (1983) Optimization by simulated annealing. Science 220(4598):671–680
Prandtstetter M, Raidl GR (2007) An integer linear programming approach and a hybrid variable neighborhood search for the car sequencing problem. Eur J Oper Res 191(3):1004–1022
Varadharajan TK, Rajendran C (2005) A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs. Eur J Oper Res 167(3):772–795
Eren T, Güner E (2008) The tricriteria flowshop scheduling problem. Int J Adv Manuf Technol 36(11):1210–1220
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Mousavi, S.M., Zandieh, M. & Yazdani, M. A simulated annealing/local search to minimize the makespan and total tardiness on a hybrid flowshop. Int J Adv Manuf Technol 64, 369–388 (2013). https://doi.org/10.1007/s00170-012-4031-5
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-012-4031-5