Scheduling Variable Maintenances and Jobs on Unrelated Parallel Machines to Minimize the Total Completion Time. Issue 4 (1st October 2016)

• Record Type: Journal Article
• Authors: Gong, Jianbo; Luo, Wenchang
• Is Part Of: American journal of mathematical and management sciences. Volume 35:Issue 4(2016)
• Page Start: 327
• Page End: 334
• Publication Date: 2016-10-01
• Subjects: Maintenance -- scheduling -- total completion time -- unrelated parallel machines; Operations research -- Periodicals; Management science -- Periodicals; Periodicals; 658.4034
• DOI: 10.1080/01966324.2016.1203849
• Languages: English
• ISSNs: 0196-6324

Abstract

SYNOPTIC ABSTRACT: We investigate an unrelated parallel-machine scheduling problem in which each machine must perform a variable mandatory maintenance prior to a given deadline. A variable maintenance means that the duration of the maintenance depends on its starting time, i.e., the later the maintenance starts, the longer it takes to complete. The task is to schedule all the jobs and determine the starting times of each maintenance such that the total completion time is minimized. We show that the problem is strongly NP-hard. Furthermore, we provide a fast heuristic algorithm, followed by a numerical example.