时间：2018年3月29日（周四）11：50 - 12：50
Title：Two-stage hybrid flowshop scheduling with simultaneous processing machines
Abstract: Simultaneous processing machines, common in processing industries such as steel and food production, can process several jobs simultaneously in the First In First Out (FIFO) manner. However, they are often highly energy-consuming. We study a new two-stage hybrid flowshop scheduling problem, with simultaneous processing machines at the first stage and a single no-idle machine with predetermined job sequence at the second stage. A mixed integer programming model and its reduced model is proposed with the objective of minimizing the total processing time to reduce energy consumption and improve production efficiency. We give a sufficient and necessary condition to construct feasible sequencing solutions, and present an effective approach to calculate the time variables for a feasible sequencing solution with the complexity O(nm), where n and m are the number of jobs and machines, respectively. These properties are integrated to formalize an algorithm framework. Under the algorithm framework, a list scheduling algorithm is presented, which can obtain optimal schedules under certain conditions. An improved heuristic is further proposed in consideration of differences of jobs in minimum processing times, and a theoretical proof is provided to show the superb performance of this improved algorithm. Time complexities of the two algorithms are both O(nlogn). Our experiments verify the efficiency of these heuristics compared with classical heuristics in the literature, and investigate the impacts of problem size and processing times.