Title :
Rescheduling Rework Jobs on Single Machine locked by initial loads
Author :
Yandong Guo ; Min Huang ; Qing Wang
Author_Institution :
Coll. of Inf. Sci. & Eng., Northeastern Univ., Shenyang, China
Abstract :
In this paper, the problem of Rescheduling Rework Jobs on Single Machine (RRJSM) is investigated. Suppose that a single machine has a set of the initial loads locked for some desired purposes. The objective of RRJSM is to minimize the maximum waiting time of rework jobs by scheduling or inserting them into the locked initial loads. Firstly, the RRJSM problem is formulated and proved to be NP-hard as for computational complexity. Secondly, two properties of RRJSM problem are addressed. Furthermore, a heuristic algorithm is designed basing on the properties and its complexity is given as well. Finally, the optimality condition of the algorithm and the judgment of optimal solution are given and proved respectively.
Keywords :
computational complexity; genetic algorithms; single machine scheduling; NP-hard computational complexity; RRJSM; computational complexity; heuristic algorithm; locked initial loads; optimal solution; rescheduling rework jobs on single machine; Algorithm design and analysis; Educational institutions; Heuristic algorithms; Job shop scheduling; Optimal scheduling; Schedules; Single machine scheduling; Heuristic algorithm; Rescheduling; Rework jobs; Waiting time;
Conference_Titel :
Service Systems and Service Management (ICSSSM), 2013 10th International Conference on
Conference_Location :
Hong Kong
Print_ISBN :
978-1-4673-4434-0
DOI :
10.1109/ICSSSM.2013.6602657
