Local search Methods to Solve The Sum of Two Objective Functions

Sarah Kamil Hanoon; Al- Zuwaini Mohammed Kadhim

Sarah Kamil Hanoon Department of Mathematics, College of Computer Science and Mathematics Thi-Qar University, Thi-Qar, Iraq
Al- Zuwaini Mohammed Kadhim Department of Mathematics, College of Computer Science and Mathematics Thi-Qar University, Thi-Qar, Iraq

Keywords: Single machine, Scheduling, Simulated Annealing, Ant colony, Hybridization.

Abstract

In this paper, the problem of sequencing a set of n jobs on single machine was considered to minimize theobjective function. The aim is to find the optimal or near optimal solution (scheduling) for the objective function consists of a sum of total late work and maximum lateness. This problem is strongly NP-hard. Simulated Annealing, Ant colony Algorithm, and usagea hybridization as a tool to solved the problem approximatelywith up to 100000 jobs in a reasonable time 10 minutes.

Downloads

Download data is not yet available.

References

Potts C. N. and Van Wassenhove L. N., “Single Machine To Minimize Total Late Work “Operations Research 40-3(1991)586-595.

Held, M., and Karp ,R.M., "A dynamic programming approach to

sequencing problems", Journal of the Society for Industrial and

Applied Mathematics 10, 196-210 (1962).

Hariri, A. M. A., Potts, C. N., & Van Wassenhove, L. N. Single machine scheduling to minimize total weighted late work. ORSA Journal on Computing, 7, 232–242. doi:10.1287/ ijoc.7.2.232.

Kethley, R. B., & Alidaee, B. (2002). Single machine scheduling to minimize total weighted late work: A comparison of scheduling rules and search algorithms. Computers & Industrial Engineering, 43, 509–528. doi:10.1016/S0360-8352(02)00123-7.

Błażewicz, J., Pesch, E., Sterna, M., & Werner, F. (2005a). The two machine flow shop problem with weighted late work criterion and common due date. European Journal of Operational Research, 165,408–415. doi:10.1016/j.ejor.2004.04.011.

Lin, B. M. T., Lin, F. C., & Lee, R. C. T. (2006). Two-machine flow-shop scheduling to minimize total late work. Engineering Optimization, 38, 501–509. doi:10.1080/03052150500420439.

Manal G. Ahmed Al-Ayoubi "A Single Machine Scheduling Problem to Minimize the Sum of Total Completion Times and Total Late Works" Al- Mustansiriyah J. Sci. Vol. 23, No 7, 2012.

Asmaa Ali Zeyad " Scheduling Jobs on a Single Machine to Minimize Bi-criteria" M.Sc thesis, Dept. of mathematics, college of Education for Pure Sciences, Thi-Qar University (2016).

Jackson, J.R.,"Scheduling a production line to minimize maximum tardiness", Research Report 43, Management Sciences Research Project, UCLA (1955).

Horn, W.A., ''Some simple scheduling algorithms'', Naval Research Logistics Quarterly, 21(1):177-185 (1974).

Hariri, A.M.A., and Potts, C.N., "Single machine scheduling with

batch set-up times to minimize maximum lateness", Annals of

Ops. Res. O, 75-92 (1997).

Christos, K., and George J.K., ''Single-machine scheduling problems with past-sequence-dependent delivery times'', Int. J. Production Economics 126. 264–266 (2010).

Habibeh, N., and Lai, S.L., ''Solving Single Machine Scheduling

Problem with Maximum Lateness Using a Genetic Algorithm'',

Journal of Mathematics Research Vol. 2, No. 3; August (2010).

Radostaw, R., '' Minimizing maximum lateness in a single machine scheduling problem with processing time based aging effects'', European J. Industrial Engineering Vol. x, No. x,xxxx Accepted 12 September (2011).

Suh-Jenq, Y., Jia-Yuarn, G., Hsin-Tao, L., and Dar-Li, Y.,''Single

machine scheduling problem past sequence dependent delivery times and deterioration and learning effects simultaneously'', ICIC International c ISSN 1349-4198 (2013).

Morteza, S., and Mehde , S., ''Minimizing Maximum Lateness in a

Single Machine Scheduling Problem with a Fixed Availability Constraint'', Scientific Research Volume: 4, Issue: 1, Pages: 155-165 (January 2015).

Araibi, S.M., "Machine Scheduling Problem to Minimize Two and Three Objectives Function", M.Sc thesis, Dept. of mathematics, college of Education for Pur Sciences,Thi-QarUniversity (2012).

Husein, N.A.,'' Machine Scheduling Problem to Minimize Multiple Objective Function'', M.Sc thesis, Dept. of Mathematics College of Education (Ibn AL-Haitham), Baghdad University (2012).

S. French, Sequencing and scheduling: An introduction to the mathematics of the job-Shop, John Wiley & Sons, New York (1982).

Dorigo, M., Maniezzo V., and Colorni ,A., "A positive feedback as a search strategy", Milan, Italy. tech. Rep. 91-016. (1991).

John E.B., and Patrick R. M., '' Ant colony optimization techniques for the vehicle routing problem'', Advanced Engineering Informatics 18 41–48, (2004).

Ali Berrichi, Farouk Yalaoui '' Efficient bi-objective ant colony approach to minimize total tardiness and system unavailability for a parallel machine scheduling problem " Int J Adv Manuf Technol. Accepted: 15 February 2013

Sami. M Araibi "Ant Colony Method to Minimize Single Machine Scheduling problem "Journal of Thi-Qar Science Vol. 6(3), Dec./2017.

Hussam A.A. Mohammed,Fathalh A. Cheachan,Hanan A. CheachanandFaria A. Cheachan"On Fuzzy Distances and Their Applications on Cost Function L ̃((C_j ) ̃,(D_j ) ̃)" Transactions on Engineering and Sciences.Vol.3, Issue 2, February 2015.

Christian Blum., '' Ant colony optimization: Introduction and recent trends'', Physics of Life Reviews 2353–373.(2005).

Hussein J.M.," Flow shop scheduling problems Using Exact and Local search methods", M.Sc. thesis University of Al-mustansiriyah, College of science, Dep. Of Mathematics (2008).

S.A. Seyed-Alagheband, H. Davoudpour, S.H. Hashemi Doulabi, M. Khatibi"Using a Modified Simulated Annealing Algorithm to Minimize Makespan in a Permutation Flow-shop Scheduling Problem with Job Deterioration"Proceedings of the World Congress on Engineering and Computer Science 2009 Vol II WCECS 2009, October 20-22, 2009, San Francisco, USA.ISBN:978-988-18210-2-7.

Sergio Fichera, Fulvio Cappadonna, Antonio Costa, Alberto Fichera"A Simulated Annealing Algorithm for Single Machine Scheduling Problem with Release Dates, Learning and Deteriorating Effects"Proceedings of the World Congress on Engineering 2013 Vol I, WCE 2013, July 3 - 5, 2013, London, U.K.

Nakandhrakumar R.S and Balachandar M"Implementation of Simulated Annealing Technique for Optimizing Job Shop Scheduling Problem" International Journal of Advanced Mechanical Engineering. ISSN 2250-3234 Volume 4, Number 2 (2014), pp. 169-174

Sergio, F. Fulvio, C. Antonio, C. Alberto, F. " A Simulated Annealing Algorithm for Single Machine Scheduling Problem with Release Dates, Learning and Deteriorating Effects" Proceedings of the World Congress on Engineering Vol I, WCE 2013, July 3 - 5, London, U.K.

Thamilselvan Rakkiannan, Balasubramanie Palanisamy "Hybridization of Genetic Algorithm with Parallel Implementation of Simulated Annealing for Job Shop Scheduling" American Journal of Applied Sciences 9 (10): 1694-1705, 2012.

AL Zuwaini M.K," A comparative Study of Local Search Methods for Some Machine Scheduling Problems with the Usage of Hybridization As A Tool"., Ph. D. thesis, University of Baghdad, College of Education (Ibn Al-Haitham), Dep. of Mathematics (2006).

A. Jamili , M.A. Shafia, R. Tavakkoli-Moghaddam "A hybridization of simulated annealing and electromagnetism-like mechanism for a periodic job shop scheduling problem" journal homepage: www.elsevier.com/locate/eswa (2010).

Kashif Akram , Khurram Kamal and Alam Zeb "Fast simulated annealing hybridized with quenching for solving job shop scheduling problem" Applied Soft Computing 49 (2016) 510–523, journal ho me page: www.elsevier.com/locate /asoc.

Abdul-Razaq, T.S., Potts C.N. and Van Wassenhove, ''A survey of

algorithms for the single machine total weighted tardiness scheduling problem'', Discrete App. Math. 26235-253(1990).