Back to results
US 11,537,995 B2Granted
Method and system for cyclic scheduling
AssigneeKing Fahd University of Petroleum and Minerals
InventorHesham K. Alfares
Life of this patent
Estimating the term…
Abstract
A method, computer software product and system for solving cyclic scheduling problems. Specifically, the present disclosure significantly improves the method in a previous patent (H. K. Alfares, 2011, “Cyclic Combinatorial Method and System”, U.S. Pat. No. 8,046,316), by eliminating a time-consuming combinatorial procedure. A procedure is described which significantly decreases the number of iterations, and hence computational time and cost. The processes of the present disclosure have many applications in cyclic workforce scheduling, cyclic transportation system scheduling, cyclic scheduling of data packet transmitting as applied to networks having a plurality of nodes and cyclic production scheduling.
Claims4
A cyclic transportation method for vehicle travel on a route, comprising:
- carrying out maintenance on a number of vehicles xj assigned to a maintenance day pattern j, for j=1, . . . , 7, of a total number of vehicles Z assigned to the route;
- receiving, by a computing machine including a computer readable memory storing program instructions and at least one processor configured to implement the program instructions, the total number of vehicles Z assigned to the route;
- receiving, by the computing machine, an objective of minimizing Z;
- converting, by the at least one processor, the objective of minimizing Z to an objective of minimizing a cost function Ws, which equals a sum of the number of vehicles xj assigned to the maintenance day pattern;
- receiving, by the computing machine, a set of known requirements ri for a number of vehicles required on a travel day i to travel on the route, for i=1, 2, . . . , 7;
- receiving, by the at least one processor, a cyclic 0−1 7×7 constraint matrix A having coefficients aij, wherein each coefficient aij equals 1, if day i is a travel day for the maintenance days pattern j, otherwise aij equals 0;
- constructing, by the at least one processor, a dual linear cost function Wd from the cost function Ws, wherein Wd equals a sum of each known requirement rj multiplied by a dual variable yj, subject to constraints Σj=17aijTyj≤1, where T represents a transpose, and yj≥0;
- maximizing the cost function Wd by:
- identifying, by the at least one processor, a total of 7 dual variables;
- determining, by the at least one processor, at least one set of m basic non-zero dual variables from the 7 dual variables;
- identifying, by the at least one processor, each set of the m basic non-zero dual variables which is a potential dominant solution;
- determining, by the at least one processor, a maximum number of non-zero coefficients Lm in each potential dominant solution;
- and
- determining, by the at least one processor, the best sets of the m basic non-zero dual variables SVm by adding a constraint ΣjϵSVmVj≤Lm−1 to each set and determining a ratio m/Lm for each set, wherein the best sets are those with a highest ratio of m/Lm, wherein the best sets provide a set of dominant solutions which determine a minimum cost of the total number of vehicles Z, including the vehicles receiving maintenance, while ensuring that a required number of vehicles run on the route each day.
11 more elements
In a network comprising a plurality of nodes in a machine environment having a cyclic production schedule in which machines are operated during ON (binary 1) hours and sleep during OFF (binary 0) hours in a 24 hour workday, the improvement consisting of:
- scheduling data packet transmission through the plurality of nodes by:
- receiving, by a computing machine including a computer readable memory storing program instructions and at least one processor configured to implement the program instructions, a total number of data packets Z;
- receiving, by the computing machine, an objective of minimizing Z;
- converting, by the at least one processor, the objective of minimizing Z to an objective of minimizing a cost function Ws, which equals a sum of the number of nodes xj assigned to the sleep pattern, for j=1, . . . , 6;
- receiving, by the computing machine, a set of known requirements ri which equals a number of nodes required to transmit during a transmit time window of 60 seconds, wherein each transmit time is 10 seconds, such that i=1, . . . , 6;
- receiving, by the at least one processor, a cyclic 0−1 6×6 constraint matrix, A, having coefficients, aij, wherein each coefficient, aij, equals 1, if i is an open transmit time window j, otherwise aij equals 0;
- constructing, by the at least one processor, a dual linear cost function, Wd, from the cost function Ws, wherein Wd equals a sum of each known requirement, rj, multiplied by a dual variable, yj, subject to constraints Σj=1naijTyj≤1, where T represents a transpose and yj≥0;
- maximizing the cost function Wd by:
- identifying, by the at least one processor, a total of 6 dual variables;
- determining, by the at least one processor, at least one set of m basic non-zero dual variables from the 6 dual variables;
- identifying, by the at least one processor, each set of the m basic non-zero dual variables which is a potential dominant solution;
- determining, by the at least one processor, a maximum number of non-zero coefficients (Lm) in each potential dominant solution;
- determining, by the at least one processor, the best sets of the m basic non-zero dual variables (SVm) by adding a constraint ΣjϵSVmVj≤Lm−1 to each set and determining a ratio m/Lm for each set, wherein the best sets are those with a highest ratio of m/Lm, wherein the best sets provide a set of dominant solutions which determine the minimum Z, wherein the minimum Z, represents a minimum number of nodes which must be active to transmit all of the data packets during the transmit time window defined by i=1, . . . , 6.
10 more elements
Dependencies are inferred from the claim text.