Parallel-machine scheduling of deteriorating jobs with potential machine disruptions |
| |
| Institution: | 1. Faculty of Science, Kunming University of Science and Technology, Kunming, China;2. Department of Logistics and Maritime Studies, The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong;1. School of Mathematics and Statistics, University of Melbourne, Melbourne, Australia;2. Faculty of Industrial and Mechanical Engineering, Qazvin Branch, Islamic Azad University (IAU), Qazvin, Iran;3. Department of Business Technology and Entrepreneurship, Swinburne Business School, Swinburne University of Technology, Hawthorn, 3122, VIC, Australia;4. Department of Computer Science and Software Engineering, School of Software and Electrical Engineering, Swinburne University of Technology, Hawthorn, 3122, VIC, Australia;5. Young Researchers and Elites Club, Qazvin Branch, Islamic Azad University (IAU), Qazvin, Iran;6. Caspian Higher Education Institute, Qazvin, Iran;1. Key Lab of Intelligent Computing and Signal Processing of Ministry of Education, Anhui University, Hefei, Anhui 230039, PR China;2. Department of Computer Science, New Jersey Institute of Technology, Newark, NJ 07102, United States;1. LCOMS, Université de Lorraine, France;2. Institut für Statistik und Operations Research, University of Graz, Austria;1. Department of Public Course, Zhongshan Torch Polytechnic, Zhongshan 528436, China;2. Faculty of Management and Economics, Dalian University of Technology, Dalian 116024, China;3. School of Science, Shenyang Aerospace University, Shenyang 110136, China |
| |
| Abstract: | We consider parallel-machine scheduling of deteriorating jobs in a disruptive environment in which some of the machines will become unavailable due to potential disruptions. This means that a disruption to some of the machines may occur at a particular time, which will last for a period of time with a certain probability. If a job is disrupted during processing by a disrupted machine and it does not need (needs) to re-start after the machine becomes available again, it is called the resumable (non-resumable) case. By deteriorating jobs, we mean that the actual processing time of a job grows when it is scheduled for processing later because the machine efficiency deteriorates over time due to machine usage and aging. However, a repaired machine will return to its original state of efficiency. We consider two cases, namely performing maintenance immediately on the disrupted machine when a disruption occurs and not performing machine maintenance. In each case, the objective is to determine the optimal schedule to minimize the expected total completion time of the jobs in both non-resumable and resumable cases. We determine the computational complexity status of various cases of the problem, and provide pseudo-polynomial-time solution algorithms and fully polynomial-time approximation schemes for them, if viable. |
| |
| Keywords: | Scheduling Deteriorating jobs Disruptive environment Fully polynomial-time approximation scheme |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
