DocumentCode :
3392980
Title :
A hybrid way to solve the task scheduling problem for multi-parallel machines with Time windows
Author :
Jianghan, Zhu ; Lining, Zhang ; Dishan, Qiu ; Haoping, Li
Author_Institution :
Coll. of Inf. Syst. & Manage., Nat. Univ. of Defense Technol., Changsha, China
Volume :
1
fYear :
2009
fDate :
19-20 Dec. 2009
Firstpage :
36
Lastpage :
39
Abstract :
Task Scheduling for Parallel Machines with Time Windows (TSPMTW) is a combinatorial optimization problem, when the number of variables and constraints on a large scale, it could become even more complex. A hybrid way combined Integer Programming (IP) with Constraint Programming (CP) techniques was presented. The theoretical basis of this approach is the common principles shared by IP and CP: strategies of searching and inference, strengthening and relaxation. In this method, the problem was decomposed through logic based Benders´ decomposition; the first part is an assignment problem which was treated as master problem, while the other is a series of single machine scheduling problem, we call it sub-problem; connections between master problem and sub-problem are general Benders´ cuts. The master problem was solved to generate the assignment scheme which had the maximum benefit, then make schedule for each machine according to the assignment scheme; if any conflict happens, Benders´ cuts were produced and sent to master problem as new constraints in the coming iterations. During the solving process of both master problem and sub-problem, the idea of integrating IP and CP tactics was implemented. This new algorithm has been tested by derived experiments under different scenarios, and these tests and comparisons yielded promising effect.
Keywords :
combinatorial mathematics; constraint handling; integer programming; single machine scheduling; combinatorial optimization problem; constraint programming; integer programming; logic based Benders decomposition; multiparallel machine; single machine scheduling; task scheduling problem; time windows; Artificial intelligence; Educational institutions; Intelligent transportation systems; Large-scale systems; Machine intelligence; Management information systems; Parallel machines; Power electronics; Single machine scheduling; Testing; Benders´ decomposition; Hybrid way; multi-parallel machines; task scheduling problem; time windows;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Power Electronics and Intelligent Transportation System (PEITS), 2009 2nd International Conference on
Conference_Location :
Shenzhen
Print_ISBN :
978-1-4244-4544-8
Type :
conf
DOI :
10.1109/PEITS.2009.5406997
Filename :
5406997
Link To Document :
بازگشت