.png){kind=icon}
.png){kind=icon}
Return
A binary multiple knapsack model for single machine scheduling with machine unavailability
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2016.02.005.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper addresses the single machine weighted number of on-time jobs scheduling problem where the machine is unavailable during one or more maintenance periods and the jobs share a common due date. It models the problem as a binary multiple knapsack (MKP), and offers an alternative proof that the problem is NP-Complete in the strong sense. Subsequently, it shows that some large-sized instances can be solved exactly within less than a second using an off-the-shelf solver. For difficult instances, the paper proposes a variable neighborhood search based heuristic V that explores the MKP nature of the problem to determine near-optima. V is dotted with two mechanisms that speed its convergence toward near global optima: a linked list data structure and a dynamic threshold acceptance criterion. Experimental results provide computational evidence of the efficiency and efficacy of V for benchmark MKP instances and for scheduling problems alike. It further discusses the robustness of V with respect to the initial solution and problem's parameters. (C) 2016 Elsevier Ltd. All rights reserved.
Keywords:
Binary multiple knapsack
Single machine scheduling
Weighted number of tardy jobs
Variable neighborhood search
Machine maintenance
Machine availability
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W