Advanced search
Publication Cover
Journal of the Operational Research Society Volume 66, 2015 - Issue 9
Submit an article Journal homepage
164
Views
17
CrossRef citations to date
0
Altmetric
General Paper

A branch and bound algorithm to minimize total tardiness of jobs in a two identical-parallel-machine scheduling problem with a machine availability constraint

Ju-Yong LeeKorea Advanced Institute of Science and Technology (KAIST)DaejeonKorea
&
Yeong-Dae KimKorea Advanced Institute of Science and Technology (KAIST)DaejeonKoreaCorrespondence[email protected]
Pages 1542-1554 | Received 22 Nov 2013, Accepted 28 Oct 2014, Published online: 21 Dec 2017

References

  • AdiriIBrunoJFrostigERinnooy-KanAHGSingle machine flow-time scheduling with a single breakdownActa Informatica198926767969610.1007/BF00288977
  • AdiriIFrostigERinnooy-KanAHGScheduling on a single machine with a single breakdown to minimize stochastically the number of tardy jobsNaval Research Logistics199138226127110.1002/1520-6750(199104)38:2<261::AID-NAV3220380210>3.0.CO;2-I
  • AkturkMSGhoshJBGunesEDScheduling with tool changes to minimize total completion time: A study of heuristics and their performanceNaval Research Logistics2003501153010.1002/nav.10045
  • AkturkMSGhoshJBGunesEDScheduling with tool changes to minimize total completion time: Basic results and SPT performanceEuropean Journal of Operational Research2004157378479010.1016/S0377-2217(03)00232-7
  • AzizogluMKircaOTardiness minimization on parallel machinesInternational Journal of Production Economics199855216316810.1016/S0925-5273(98)00034-6
  • BakerKRIntroduction to Sequencing and Scheduling1974
  • BirgeJFrenkJBGMittenthalJRinnooy-KanAHGSingle-machine scheduling subject to stochastic breakdownsNaval Research Logistics199037566167710.1002/1520-6750(199010)37:5<661::AID-NAV3220370506>3.0.CO;2-3
  • ChenJSSingle-machine scheduling with flexible and periodic maintenanceJournal of the Operational Research Society200657670371010.1057/palgrave.jors.2602043
  • ChenWJMinimizing total flow time in the single-machine scheduling problem with periodic maintenanceJournal of the Operational Research Society200657441041510.1057/palgrave.jors.2601998
  • ChenJSOptimization models for the tool change scheduling problemOmega200836588889410.1016/j.omega.2006.04.006
  • ChenWJMinimizing number of tardy jobs on a single machine subject to periodic maintenanceOmega200937359159910.1016/j.omega.2008.01.001
  • ChoiYCKimYDTool replacement policies for a machining center producing multiple types of products with distinct due datesInternational Journal of Production Research200139590792110.1080/00207540010011054
  • ChuCA branch and bound algorithm to minimize total tardiness with different release datesNaval Research Logistics199239226528310.1002/1520-6750(199203)39:2<265::AID-NAV3220390209>3.0.CO;2-L
  • DasKLashkariRSSenguptaSIntegrating machine reliability and preventive maintenance planning in manufacturing cell designIndustrial Engineering and Management Systems200872114125
  • Dell’AmicoMMartelloSBounds for the cardinality constrained P∣∣Cmax problemJournal of Scheduling20014312313810.1002/jos.68
  • DuJLeungJYTMinimizing total tardiness on one machine is NP-hardMathematics of Operations Research199015348349510.1287/moor.15.3.483
  • EckerKHGuptaJNDScheduling tasks on a flexible manufacturing machine to minimize tool change delaysEuropean Journal of Operational Research2005164362763810.1016/j.ejor.2003.12.025
  • FrostigEA note on stochastic scheduling on a single machine subject to breakdown—the preemptive repeat modelProbability in the Engineering and Information Sciences19915334935410.1017/S0269964800002138
  • GharbiAHaouariMOptimal parallel machines scheduling with availability constraintsDiscrete Applied Mathematics20051481638710.1016/j.dam.2004.12.003
  • GrahamRLLawlerELLenstraJKRinnooy-KanAHGOptimization and approximation in deterministic sequencing and scheduling: A surveyAnnals of Discrete Mathematics1979528732610.1016/S0167-5060(08)70356-X
  • HoJCWongJSMakespan minimization for m parallel identical processorsNaval Research Logistics199542693594810.1002/1520-6750(199509)42:6<935::AID-NAV3220420606>3.0.CO;2-D
  • HongSSParkJHLieCHOptimal preventive maintenance policy with cost-dependent improvement factorJournal of the Korean Institute of Industrial Engineers2010362108116
  • HsuCJLowCSuCTA single-machine scheduling problem with maintenance activities to minimize makespanApplied Mathematics and Computation2010215113929393510.1016/j.amc.2009.11.040
  • KimYDMinimizing total tardiness in permutation flowshopsEuropean Journal of Operational Research199585354155510.1016/0377-2217(94)00029-C
  • KondakciSAzizogluMKircaOAn efficient algorithm for the single machine tardiness problemInternational Journal of Production Economics199436221321910.1016/0925-5273(94)90026-4
  • KoulamasCDecomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problemNaval Research Logistics199744110912510.1002/(SICI)1520-6750(199702)44:1<109::AID-NAV7>3.0.CO;2-E
  • LeeCYMachine scheduling with an availability constraintJournal of Global Optimization199693–439541610.1007/BF00121681
  • LeeCYChenZLScheduling jobs and maintenance activities on parallel machinesNaval Research Logistics200047214516510.1002/(SICI)1520-6750(200003)47:2<145::AID-NAV5>3.0.CO;2-3
  • LeeCYLimanSDCapacitated two-parallel machines scheduling to minimize sum of job completion timesDiscrete Applied Mathematics199341321122210.1016/0166-218X(90)90055-H
  • LeeHParkYJHurSA preventive maintenance scheduling model of the cluster toolIE Interfaces201225112713310.7232/IEIF.2012.25.1.127
  • LeeJYKimYDMinimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenanceComputers and Operations Research20123992196220510.1016/j.cor.2011.11.002
  • LeeSHLeeIGHeuristic algorithm for the single machine scheduling with periodic maintenanceJournal of the Korean Institute of Industrial Engineers2008343318327
  • LenstraJKRinnooy-KanAHGBruckerPComplexity of machine scheduling problemsAnnals of Discrete Mathematics1977134336210.1016/S0167-5060(08)70743-X
  • LevinAMosheiovGSarigAScheduling a maintenance activity on parallel identical machinesNaval Research Logistics2009561334110.1002/nav.20324
  • LiaoCJChenWJSingle-machine scheduling with periodic maintenance and nonresumable jobsComputers and Operations Research20033091335134710.1016/S0305-0548(02)00074-6
  • LiaoCJChenCMLinCHMinimizing makespan for two parallel machines with job limit on each availability intervalJournal of the Operational Research Society200758793894710.1057/palgrave.jors.2602209
  • LiaoCJShyurDLLinCHMakespan minimization for two parallel machines with an availability constraintEuropean Journal of Operational Research2005160244545610.1016/j.ejor.2003.08.034
  • LinCHLiaoCJMakespan minimization for two parallel machines with an unavailable period on each machineInternational Journal of Advanced Manufacturing Technology2007339–101024103010.1007/s00170-006-0524-4
  • MellouliRSadfiCChuCKacemIIdentical parallel-machine scheduling under availability constraints to minimize the sum of completion timesEuropean Journal of Operational Research200919731150116510.1016/j.ejor.2008.03.043
  • PinedoMRammouzEA note on stochastic scheduling on a single machine subject to breakdown and repairProbability in the Engineering and Information Sciences198821414910.1017/S0269964800000619
  • PottsCNVan WassenhoveLNA branch and bound algorithm for the total weighted tardiness problemOperations Research198533236337710.1287/opre.33.2.363
  • QiXChenTTuFScheduling the maintenance on a single machineJournal of the Operational Research Society199950101071107810.1057/palgrave.jors.2600791
  • RachamaduguRMVA note on the weighted tardiness problemOperations Research198735345045210.1287/opre.35.3.450
  • SchallerJNote on Shim and Kim’s lower bounds for scheduling on identical parallel machines to minimize total tardinessEuropean Journal of Operational Research2009197142242610.1016/j.ejor.2008.07.005
  • ShimSOKimYDScheduling on parallel identical machines to minimize total tardinessEuropean Journal of Operational Research2007177113514610.1016/j.ejor.2005.09.038
  • TanakaSArakiMA branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machinesInternational Journal of Production Economics2008113144645810.1016/j.ijpe.2007.10.006
  • WangJJWangJBLiuFParallel machines scheduling with a deteriorating maintenance activityJournal of the Operational Research Society201162101898190210.1057/jors.2010.143
  • XuDSunKLiHParallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespanComputers and Operations Research20083541344134910.1016/j.cor.2006.08.015
  • YalaouiFChuCParallel machine scheduling to minimize total tardinessInternational Journal of Production Economics200276326527910.1016/S0925-5273(01)00175-X

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Order Reprints Request Corporate Permissions

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

Request Academic Permissions

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.

Related research

People also read lists articles that other readers of this article have read.

Recommended articles lists articles that we recommend and is powered by our AI driven recommendation engine.

Cited by lists all citing articles based on Crossref citations.
Articles with the Crossref icon will open in a new tab.