Workflow Scheduling With Learning And Forgetting Effects In Cloud Manufacturing

Cloud manufacturing can provide a variety of manufacturing services on demand.Task and resource scheduling is key to improve the quality of manufacturing services.This thesis considers the scheduling problem with deadline-constrained workflow and learning-forgetting effect of services in cloud manufacturing to minimize the total cost.There are three challenges in the problem:(i)The deadline constraint of workflow makes it difficult to achieve a balance between makespan and the total cost.A lower rental cost usually leads to a longer workflow makespan,which may violate the deadline constraint.However,a shorter workflow makespan usually requires service resources with a higher rental price,resulting in a higher total cost.(ii)The impact of logistics cost on scheduling results leads the problem much hard to optimize the total cost.Distributed parallel execution of tasks can reduce the risk of deadline violation,but it may increase the logistics cost between distributed manufacturing resources.On the contrary,optimizing the logistics cost might sacrifice the task parallelism.(iii)Reasonable learning and forgetting effects are key to minimize the execution cost.Task execution on different service resources could result in variable execution time by different learning and forgetting effects.For the problem under study,a model of learning-forgetting effect is established and two heuristic workflow scheduling algorithms with different optimization ideas are proposed,including Workflow Scheduling based on Task Scheduling Sequence Adjustment(WSTSSA)and Workflow Scheduling based on PCH(WSPCH).The WSTSSA algorithm includes four algorithm components to achieve a balance between makespan and the total cost: task sub-deadline division,task scheduling sequence generation,service allocation and scheduling result adjustment,and various rules are developed for task sub-deadline division and task scheduling sequence generation.The WSPCH algorithm consists of three steps: task sub-deadline division,clustering and service allocation.It can reduce the logistics cost by clustering workflow tasks and assigning them to the same service.It also takes the learning-forgetting effect into account at the same time to optimize the execution cost.In order to evaluate the performance of proposed algorithms,the multi-factor analysis of variance(ANOVA)technique is adopted to calibrate involved algorithm components and parameters.The proposed algorithms are analyzed and compared with the related workflow scheduling algorithms.Experimental results indicate that the performance of WSTSSA and WSPCH is very close,and both of them outperform the compared algorithms under different workflow instances.WSTSSA is more suitable for the workflow scheduling scenario with fewer tasks and looser deadlines,while WSPCH is more suitable for the cases with more tasks and more urgent deadlines.In terms of the logistics cost,the performance of WSTSSA is better than WSPCH.WSPCH outperforms WSTSSA in optimizing the execution cost.