A work assistance device for assisting a setup work in a system having a plurality of lines for producing a plurality of types of products, each of the lines requesting the setup work for producing one of the types products after switching from production of another one of the types of products, the work assistance device comprising: an acquisition unit configured to acquire, among production plan information including setup time of each type of product, production time of each type of product, and a production order of the type of product in each line, production plan information on each type of product for which the setup work is yet to be performed, from a storage unit; and a determination unit (38, 40) configured to formulate a problem of optimizing an execution order of the setup work as an integer programming problem based on the acquired production plan information and predetermined restrictions, and to determine the execution order of the setup work for each type of product using an integer programming problem solver, characterised in that the determination unit (38, 40) is configured to calculate the earliest time when the setup work for the type of product in each line becomes executable based on the production plan information, and if a difference between the earliest time when the setup work for a first type of product in a first line becomes executable and the earliest time when the setup work for a second type of product in a second line other than the first line becomes executable is equal or greater than a given threshold value, the determination unit (38, 40) is configured to determine that the setup work for the first type of product is executed before the setup work for the second type of product, and then, the determination unit (38, 40) is configured to determine the execution order of the setup work for each type of product using the integer programming problem solver. an acquisition unit configured to acquire, among production plan information including setup time of each type of product, production time of each type of product, and a production order of the type of product in each line, production plan information on each type of product for which the setup work is yet to be performed, from a storage unit; and a determination unit (38, 40) configured to formulate a problem of optimizing an execution order of the setup work as an integer programming problem based on the acquired production plan information and predetermined restrictions, and to determine the execution order of the setup work for each type of product using an integer programming problem solver, characterised in that the determination unit (38, 40) is configured to calculate the earliest time when the setup work for the type of product in each line becomes executable based on the production plan information, and if a difference between the earliest time when the setup work for a first type of product in a first line becomes executable and the earliest time when the setup work for a second type of product in a second line other than the first line becomes executable is equal or greater than a given threshold value, the determination unit (38, 40) is configured to determine that the setup work for the first type of product is executed before the setup work for the second type of product, and then, the determination unit (38, 40) is configured to determine the execution order of the setup work for each type of product using the integer programming problem solver.