Two-agent scheduling in open shops subject to machine availability and eligibility constraints
Abstract: The aims of this
article are to develop a new mathematical formulation and a new heuristic for
the problem of preemptive two-agent scheduling in open shops subject to machine
maintenance and eligibility constraints.
Design/methodology: Using the ideas of minimum cost flow network and
constraint programming, a heuristic and a network based linear programming are
proposed to solve the problem.
Findings: Computational experiments show that the heuristic generates a
good quality schedule with a deviation of 0.25% on average from the optimum and
the network based linear programming model can solve problems up to 110 jobs
combined with 10 machines without considering the constraint that each
operation can be processed on at most one machine at a time. In order to
satisfy this constraint, a time consuming Constraint Programming is proposed.
For n = 80 and m = 10, the average execution time for the combined models
(linear programming model combined with Constraint programming) exceeds two
hours. Therefore, the heuristic algorithm we developed is very efficient and is
in need.
Practical implications: Its practical implication occurs in TFT-LCD and
E-paper manufacturing wherein units go through a series of diagnostic tests
that do not have to be performed in any specified order.
Originality/value: The main contribution of the article is to split the
time horizon into many time intervals and use the dispatching rule for each
time interval in the heuristic algorithm, and also to combine the minimum cost
flow network with the Constraint Programming to solve the problem optimally.
Keywords: Scheduling,
Two-agent, Open shop, Machine availability and eligibility, Constraint
programming
Author: Ling-Huey Su,
Ming-Chih Hsiao
Journal Code: jptindustrigg150048
