Exact algorithms for single-machine scheduling problems with a variable maintenance. (August 2016)

• Record Type: Journal Article
• Authors: Ying, Kuo-Ching; Lu, Chung-Cheng; Chen, Jhao-Cheng
• Is Part Of: Computers & industrial engineering. Volume 98(2016)
• Page Start: 427
• Page End: 433
• Publication Date: 2016-08
• Subjects: Scheduling -- Variable maintenance -- Exact algorithms; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2016.05.037
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: We deal with single-machine scheduling problems (SMSPs) with a variable machine maintenance. The four SMSPs have different objectives. We propose polynomial-time exact algorithms for the four SMSPs. Abstract: This paper deals with four single-machine scheduling problems (SMSPs) with a variable machine maintenance. The objectives of the four SMSPs are to minimize mean lateness, maximum tardiness, total flow time and mean tardiness, respectively. These four SMSPs are important in the literature and in practice. This study proposes an exact algorithm with the computational complexity O ( n 2 ) for each of the four SMSPs. In addition to the given jobs, the machine maintenance activity between two consecutive jobs is optimally scheduled.