Minimizing maximum earliness in single-machine scheduling with flexible maintenance time

Document Type : Article

Authors

1 Department of Industrial Engineering, Golpayegan University of Technology, Golpayegan, P.O. Box 87717-65651, Iran

2 Department of Industrial and Systems Engineering, Isfahan University of Technology, Isfahan, P.O. Box 84156-83111, Iran

3 Faculty of Engineering, Department of Industrial Engineering, Urmia University, Urmia, P.O. Box 57561-15311, Iran.

Abstract

We consider minimizing the maximum earliness in the single-machine scheduling problem with flexible maintenance. In this problem, preemptive operations are not allowed, the machine should be shut down to perform maintenance, tool changing or resetting takes a constant time, and the time window inside which maintenance should be performed is prede ned. We show that the problem is NP-hard. Afterward, we
propose some dominance properties and an ecient heuristic method to solve the problem. Also, we propose a branch-and-bound algorithm, in which our heuristic method, the lower bound, and the dominance properties are incorporated. The algorithm is computationally examined using 3,840 instances up to 14,000 jobs. The results impressively show that the proposed heuristic algorithm obtains the optimal solution in about 99.5% of the cases using an ordinary processor in a matter of seconds at most.

Keywords

Main Subjects

Scientia Iranica
Volume 24, Issue 4
Transactions on Industrial Engineering (E)
July and August 2017
Pages 2082-2094

Files

History

  • Receive Date: 15 August 2015
  • Revise Date: 15 April 2016
  • Accept Date: 28 June 2016

Share

How to cite

Statistics