tailieunhanh - Minimizing makespan of personal scheduling problem in available time -windows with split min and setup time constraints

This paper deals with personal scheduling problem in available time-windows with splitmin and setup-time constraints. The jobs are splittable into sub-jobs and a common lower bound on the size of each sub-job is imposed. The objective function aims to find a feasible schedule that minimizes the total completion time of all jobs. | Journal of Computer Science and Cybernetics, , (2018), 97–111 DOI MINIMIZING MAKESPAN OF PERSONAL SCHEDULING PROBLEM IN AVAILABLE TIME-WINDOWS WITH SPLIT-MIN AND SETUP-TIME CONSTRAINTS* TRANG HONG SON1,2 , TRAN VAN LANG3 , NGUYEN HUYNH-TUONG1 1 Ho Chi Minh City University of Technology, Vietnam 2 Hoa 3 Institute Sen University, Vietnam of Applied Mechanics and Informatics, VAST 2 Abstract. This paper deals with personal scheduling problem in available time-windows with splitmin and setup-time constraints. The jobs are splittable into sub-jobs and a common lower bound on the size of each sub-job is imposed. The objective function aims to find a feasible schedule that minimizes the total completion time of all jobs. The proposed scheduling problem was proved to be strongly N P -hard by a reduction to previous problem in the preliminary results. We propose in this paper an exact method based on MILP model to find optimal solution, some heuristics to find feasible solution and a meta-heuristic based on tabu search algorithm to find good solution. The computational results show the performance of proposed exact method, some heuristics and tabu search algorithm. Keywords. Splitting-job, available time-window, setup-time, assignment approach, SPT/LPT rule, tabu search algorithm. 1. INTRODUCTION In everyday life, there are many things that people need to carry out (called job), for instance, writing up the lesson plan, teaching, checking and correcting students’ homework, writing tests, doing research and so on are jobs of a teacher. Each job has a processing-time and a preparation time (or setup-time in literature). The preparation time presents the period to recuperate the job status from the last execution while this job can be split in several sub-jobs. For example, when the teacher wants to evaluate the student works from examination, they cannot do marking for hundreds of students at once.

TỪ KHÓA LIÊN QUAN
crossorigin="anonymous">
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.