Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Soft Computing
Published in: Soft Computing 4/2016

24-01-2015 | Methodologies and Application

Using a branch-and-bound and a genetic algorithm for a single-machine total late work scheduling problem

Authors: Chin-Chia Wu, Yunqiang Yin, Wen-Hsiang Wu, Hung-Ming Chen, Shuenn-Ren Cheng

Published in: Soft Computing | Issue 4/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Scheduling with learning effects has received a lot of research attention lately. On the other hand, it is commonly seen that time restrictions are usually modeled by due dates or deadlines and the quality of schedules is estimated with reference to these parameters. One of the performance measures involving due dates is the late work criterion, which is relatively unexplored. Thus, we study a single-machine scheduling problem with a position-based learning effect. The objective is to minimize the total late work, where the late work for a job is the amount of processing of this job that is performed after its due date. We attempt to develop a branch-and-bound algorithm incorporating with some dominance rules and a lower bound for the optimal solution. For saving computational time, we also propose three heuristic-based genetic algorithms for the near-optimal solution. Finally, the computational results of proposed algorithms are also provided.
previous article Fuzzy measure identification for criteria coalitions using linguistic information
next article Modeling and implementation of Z-number

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
Bachman A, Janiak A (2004) Scheduling jobs with position-dependent processing times. J Oper Res Soc 55:257–264CrossRefMATH
Beasley D, Bull D, Martin RR (1993) An overview of genetic algorithms, part 1: fundamentals. J Univ Comput 15:58–69
Bean JC (1994) Genetic algorithms and random keys for sequencing and optimization. ORSA J Comput 6:154–160CrossRefMATH
Besbes W, Teghem J, Loukil T (2010) Scheduling hybrid flow shop problem with non-fixed availability constraint. Eur J Ind Eng 4(4):413–433CrossRefMATH
Biskup D (1999) Single-machine scheduling with learning considerations. Eur J Oper Res 115:173–178CrossRefMATH
Blazewicz J (1984) Scheduling preemptible tasks on parallel processors with information loss. Technique et Science Informatiques 3:415–420MathSciNetMATH
Blazewicz J, Pesch E, Sterna M, Werner F (2005) A comparison of solution procedures for two-machine flow shop scheduling with late work criterion. Comput Ind Eng 49:611–624CrossRefMATH
Blazewicz J, Pesch E, Sterna M, Werner F (2008) Metaheuristic approaches for the two-machine flow-shop problem with weighted late work criterion and common due date. Comput Oper Res 35:574–599CrossRefMATH
Bryan Kethley R, Alidaee B (2002) Single machine scheduling to minimize total weighted late work: a comparison of scheduling rules and search algorithms. Comput Ind Eng 43:509–528CrossRef
Chen CL, Vempati VS, Aljaber N (1995) An application of genetic algorithms for flow shop problems. Eur J Oper Res 80:389–396CrossRef
Chen JS, Pan JCH, Lin CM (2008) A hybrid genetic algorithm for the reentrant flow-shop scheduling problem. Expert Syst Appl 34:570–577CrossRef
Cheng TCE, Cheng S-R, Wu W-H, Hsu P-H, Wu C-C (2011) A two-agent single-machine scheduling problem with truncated sum-of-processing- times-based learning considerations. Comput Ind Eng 60:534–541CrossRef
Essafi I, Matib Y, Dauzere-Peres S (2008) A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem. Comput Oper Res 35:2599–2616MathSciNetCrossRefMATH
Etiler O, Toklu B, Atak M, Wilson J (2004) A genetic algorithm for flow shop scheduling problems. J Oper Res Soc 55(8):830–835CrossRefMATH
French S (1982) Sequencing and scheduling: an introduction to the mathematics of the job-shop. Ellis Horwood Ltd., ChichesterMATH
Falkenauer E, Bouffoix S (1991) A genetic algorithm for job shop. In: Proceedings of the 1991 IEEE international conference on robotics and automation
Janiak A, Rudek R (2010) A note on a makespan minimization problem with a multi-ability learning effect. Omega 38(3–4):213–217CrossRef
Karthikeyan P, Baskar S, Alphones A (2013) Improved genetic algorithm using different genetic operator combinations (GOCs) for multicast routing in ad hoc networks. Soft Comput 17:1563–1572CrossRef
Koulamas C, Kyparisis GJ (2007) Single-machine and two-machine flowshop scheduling with general learning functions. Eur J Oper Res 178:402–407MathSciNetCrossRefMATH
Kuo WH, Yang DL (2006) Minimizing the total completion time in a single-machine scheduling problem with a time- dependent learning effect. Eur J Oper Res 174(2):1184–1190MathSciNetCrossRefMATH
Manaa A, Chu C (2010) Scheduling multiprocessor tasks to minimise the makespan on two dedicated processors. Eur J Ind Eng 4(3):265–279CrossRef
Moore JM (1968) An n-job, one machine sequencing algorithm for minimizing the number of late jobs. Manag Sci 15:102–109CrossRefMATH
Nawaz M, Enscore EE, Ham I (1983) A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega 11:91–95CrossRef
Pesch E, Sterna M (2009) Late work minimization in flow shops by a genetic algorithm. Comput Ind Eng 57:1202–1209CrossRef
Sterna M (2007a) Late work minimization in a small flexible manufacturing system. Comput Ind Eng 52:210–228CrossRef
Sterna M (2007b) Dominance relations for two-machine flow shop problem with late work criterion. Bull Pol Acad Sci Tech Sci 55(1):59–69MATH
Sterna M (2011) A survey of scheduling problems with late work criteria. Omega 39:120–129CrossRef
Sterna M, Blazewicz J (2007) Genetic algorithm for late work minimization in a flow shop system. MISTA, pp 455–462
Toksari MD, Oron D, Güner E (2009) Single machine scheduling problems under the effects of nonlinear deterioration and time-dependent learning. Math Comput Model 50:401–406MathSciNetCrossRefMATH
Wang JB (2010) Single-machine scheduling with a sum-of-actual-processing-time-based learning effect. J Oper Res Soc 61:172–177
Wang J-B, Sun L-H, Sun L-Y (2010a) Single machine scheduling with a learning effect and discounted costs. Int J Adv Manuf Technol 49:1141–1149CrossRef
Wang J-B, Sun L-H, Sun L-Y (2010b) Scheduling jobs with an exponential sum-of-actual-processing-time based learning effect. Comput Math Appl 60:2673–2678MathSciNetCrossRefMATH
Wang J-B, Wang M-Z (2010) Single machine multiple common due dates scheduling with learning effects. Comput Math Appl 60:2998–3002MathSciNetCrossRefMATH
Wang J-B, Li J-X (2011) Single machine past-sequence-dependent setup times scheduling with general position-dependent and time-dependent learning effects. Appl Math Model 35:1388–1395MathSciNetCrossRefMATH
Wang J-B, Wang C (2011a) Single-machine due-window assignment problem with learning effect and deteriorating jobs. Appl Math Model 35:4017–4022MathSciNetCrossRefMATH
Wang J-B, Wang M-Z (2011b) Worst-case behavior of simple sequencing rules in flow shop scheduling with general position-dependent learning effects. Ann Oper Res 191:155–169MathSciNetCrossRefMATH
Wang J-B, Wang M-Z, Ji P (2012) Scheduling jobs with processing times dependent on position, starting time and allotted resource. Asia Pac J Oper Res 29(5):1250030 (p 15 )MathSciNetCrossRefMATH
Wang J-B, Liu L, Wang C (2013a) Single machine SLK/DIF due window assignment problem with learning effect and deteriorating jobs. Appl Math Model 37:8394–8400MathSciNetCrossRef
Wang X-Y, Zhou Z, Zhang X, Ji P, Wang J-B (2013b) Several flow shop scheduling problems with truncated position-based learning effect. Comput Oper Res 40:2906–2929MathSciNetCrossRef
Wright TP (1936) Factors affecting the cost of airplanes. J Aeronaut Sci 3:122–128CrossRef
Wu C-C, Hsu P-H, Chen J-C, Wang N-S (2011) Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times. Comput Oper Res 38:1025–1034MathSciNetCrossRefMATH
Yang SJ, Hsu CJ, Yang DL (2010) Parallel-machine scheduling with setup and removal times under consideration of the learning effect. J Chin Inst Ind Eng 27(5):372–378
Yang S-J, Yang D-L (2011) Single-machine scheduling simultaneous with position-based and sum-of-processing-times-based learning considerations under group technology assumption. Appl Math Model 35:2068–2074MathSciNetCrossRefMATH
Yang S-J, Yang D-L (2012) Scheduling problems with past-sequence-dependent delivery times and learning effects. J Oper Res Soc 63:1508–1515CrossRef
Yin N, Wang X-Y (2011) Single machine scheduling with controllable processing times and learning effect. Int J Adv Manuf Technol 54:743–748CrossRef
Yin Y, Xu D, Wang J (2010) Single-machine scheduling with a general sum-of-actual-processing-times-based and job-position-based learning effect. Appl Math Model 34(11):3623–3630MathSciNetCrossRefMATH
Ying K-C, Lin S-W, Lu C-C (2011) Cell formation using a simulated annealing algorithm with variable neighbourhood. Eur J Ind Eng 5(1):22–42CrossRef
Metadata
Title
Using a branch-and-bound and a genetic algorithm for a single-machine total late work scheduling problem
Authors
Chin-Chia Wu
Yunqiang Yin
Wen-Hsiang Wu
Hung-Ming Chen
Shuenn-Ren Cheng
Publication date
24-01-2015
Publisher
Springer Berlin Heidelberg
Published in
Soft Computing / Issue 4/2016
Print ISSN: 1432-7643
Electronic ISSN: 1433-7479
DOI
https://doi.org/10.1007/s00500-015-1590-z

Other articles of this Issue 4/2016

Soft Computing 4/2016 Go to the issue

Methodologies and Application

A particle swarm inspired cuckoo search algorithm for real parameter optimization

Methodologies and Application

Integrated rescheduling and preventive maintenance for arrival of new jobs through evolutionary multi-objective optimization

Methodologies and Application

Decompositional independent component analysis using multi-objective optimization

Methodologies and Application

Fuzzy measure identification for criteria coalitions using linguistic information

Foundations

Symmetric triangular approximations of fuzzy numbers under a general condition and properties

Methodologies and Application

Co-evolution-based immune clonal algorithm for clustering

Premium Partner

    Image Credits