A greedy algorithm for scheduling tasks on production lines

Production scheduling activities allocates tasks to achieve efficient or optimal utilization of the system configuration. Due to the large combinatorial complexity of most real-world scheduling and resource allocation problems, true optimization is very difficult, requiring the consideration of numerous constraints and objectives. Heuristic solution methods are concerned to minimize the total project duration, without violating the priority constraints. The greedy algorithm presented in this paper uses a systematic partition of the tasks to be executed, scheduling tasks and communication loads to the production lines. The algorithm is suitable for solving problems with arbitrary execution and transmisison times and is applicable on systems with arbitrary topologies of the communication network, scheduling hundreds of tasks on a limited number of production lines. The paper uses terms of graph theory to model the scheduling problem and is completed with a numerical example of a small task graph. The effectiveness of the proposed algorithm is demonstrated through a comparison between scheduling results obtained with the proposed method and those obtained with sequential and random methods.