Scheduling n jobs on one machine to minimize the maximum tardiness with minimum number

The “one machine” scheduling problem is considered with the dual objective of minimizing the maximum tardiness with minimum number of tardy jobs. A simple procedure is introduced to obtain an optimal schedule with minimum “maximum tardiness” when the set of nontardy jobs is specified. A branch and bound algorithm is presented to obtain the optimal schedule that minimizes the maximum tardiness with minimum number of tardy jobs. A condition is also given to identify an initial set of early jobs. Several theorems are formulated and proved in order to justify the elimination of much branching.     

Minimizing the number of tardy jobs on a proportionate flowshop with general position-dependent processing times

In various real life scheduling systems job processing times vary according to the number of jobs previously processed. The vast majority of studies assume a restrictive functional form to describe job processing times. In this note, we address a scheduling problem with the most general job processing time functions. The machine setting assumed is an m-machine proportionate flowshop, and the objective function is minimum number of tardy jobs. We show that the problem can be formulated as a bottleneck assignment problem with a maximum cardinality constraint. An efficient polynomial time (O(n⁴ log n)) solution is introduced.     

Minimizing the number of tardy jobs in the flowshop problem with operation and resource flexibility

In this paper, we propose a reformulation for the flowshop problem based on the concept of operation to workstation flexibility. While we assume a fixed sequence of operations in the reformulation, the “location” of each operation within the flow is not fixed. The proposed flowshop problem is important because the effective use of this flexibility can lead to significant changes in production performance. Solving the proposed problem involves two sub-problems: assignment of operations to workstations and sequencing of the jobs. We present a lower bound procedure and efficient solution approaches to solve each sub-problem. Furthermore, an improvement method based on neighborhood search and simulated annealing is implemented. A set of experiments is analyzed under different combinations of the proposed heuristics achieving high quality results. These experiments demonstrate that the heuristic factor is of significance for the problem.     

Deteriorating job scheduling to minimize the number of late jobs with setup times

Deteriorating jobs scheduling problems have been widely studied recently. However, research on scheduling problems with deteriorating jobs has rarely considered explicit setup times. With the current emphasis on customer service and meeting the promised delivery dates, we consider a single-machine scheduling problem to minimize the number of late jobs with deteriorating jobs and setup times in this paper. We derive some dominance properties, a lower bound, and an initial upper bound by using a heuristic algorithm to speed up the search process of the branch-and-bound algorithm. Computational experiments show that the algorithm can solve instances up to 1000 jobs in a reasonable amount of time.     

Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective

In this paper, we minimize the weighted and unweighted number of tardy jobs on a single batch processing machine with incompatible job families. We propose two different mixed integer linear programming (MILP) formulations based on positional variables. The second formulation does not contain a big-M coefficient. Two iterative schemes are discussed that are able to provide tighter linear programming bounds by reducing the number of positional variables. Furthermore, we also suggest a random key genetic algorithm (RKGA) to solve this scheduling problem. Results of computational experiments are shown. The second MILP formulation is more efficient with respect to lower bounds, while the first formulation provides better upper bounds. The iterative scheme is effective for the weighted case. The RKGA is able to find high-quality solutions in a reasonable amount of time.     

Graph construction with the maximum number of trees by continuous edge addition

A simple computational algorithm is presented to construct a graph with the maximum number of trees by adding edges one by one. The number of trees of a graph would become an index to estimate the overall reliability of probabilistic communication networks with the same link probabilities. Our procedure, Max-trees, selects one edge that gives the maximum number of trees among edges not included in the original graph. This process is continuously repeated at each step of adding an edge, when we get the sequence of new edges to be added. As examples of the execution results, the edge sequence and the maximum number of trees are shown for two types of starting graph, which are a tree of series edges and a star-shaped tree for nodes n = 7 and 8. To see how many trees these graphs have, the minimum numbers of trees for graphs with the same number of nodes and edges are similarly calculated by the minimum-version algorithm Min-trees. An edge sequence of Max-trees makes long cycles, and that of Min-trees makes cycles of three for as long as possible. The ratio of the maximum number of trees to the minimum number of trees is about 1 to 6 for these examples. This work was presented in part at the 11th International Symposium on Artificial Life and Robotics, Oita, Japan, January 23–25, 2006     

Setting due dates to minimize the total weighted possibilistic mean value of the weighted earliness-tardiness costs on a single machine

In this paper, it is investigated how to sequence jobs with fuzzy processing times and predict their due dates on a single machine such that the total weighted possibilistic mean value of the weighted earliness-tardiness costs is minimized. First, an optimal polynomial time algorithm is put forward for the scheduling problem when there are no precedence constraints among jobs. Moreover, it is shown that if general precedence constraints are involved, the problem is NP-hard. Then, four reduction rules are proposed to simplify the constraints without changing the optimal schedule. Based on these rules, an optimal polynomial time algorithm is proposed when the precedence constraint is a tree or a collection of trees. Finally, a numerical experiment is given.