𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A heuristic approach to bicriteria scheduling

✍ Scribed by M. Murat Köksalan

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
321 KB
Volume
46
Category
Article
ISSN
0894-069X

No coin nor oath required. For personal study only.

✦ Synopsis

We consider the problem of sequencing jobs on a single machine while minimizing a nondecreasing function of two criteria. We develop a heuristic procedure that quickly finds a good solution for bicriteria scheduling. The procedure is based on using several arcs in the criterion space that are representative of the possible locations of nondominated solutions. By sampling a small number of points on these arcs, a promising point is identified in the criterion space for each arc. An efficient sequence in the neighborhood of each of the promising points is found and the best of these efficient sequences is selected as the heuristic solution. We implement the procedure for two different bicriteria scheduling problems: (i) minimizing total flowtime and maximum tardiness and (ii) minimizing total flowtime and maximum earliness. The computational experience on a wide variety of problem instances show that the heuristic approach is very robust and yields good solutions.

📜 SIMILAR VOLUMES

A mixed evolutionary/heuristic approach
A mixed evolutionary/heuristic approach to shape optimization
✍ R. Le Riche; G. Cailletaud 📂 Article 📅 1998 🏛 John Wiley and Sons 🌐 English ⚖ 380 KB 👁 2 views

The problem of ÿnding the optimal shape of a continuous structure is addressed using, alternatively, heuristic, evolutionary and mixed evolutionary and heuristic optimization strategies. Boundaries are represented by B-splines. Two heuristics for minimizing the weight of a structure subject to limit

A scheduling approach to parallel harmon
A scheduling approach to parallel harmonic balance simulation
✍ Rhodes, David L.; Gerasoulis, Apostolos 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 309 KB 👁 1 views

Rather than approach the parallelization of the harmonic balance simulation method numerically, a novel scheduling-oriented approach is described. The technique leverages circuit substructure to expose potential parallelism in the form of a directed, acyclic graph (dag) of computations. This dag is

Optimal shift scheduling: A branch-and-p
Optimal shift scheduling: A branch-and-price approach
✍ Anuj Mehrotra; Kenneth E. Murphy; Michael A. Trick 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB 👁 1 views

We present a branch-and-price technique for optimal staff scheduling with multiple rest breaks, meal break, and break windows. We devise and implement specialized branching rules suitable for solving the set covering type formulation implicitly, using column generation. Our methodology is more widel

A heuristic method based on a statistica
A heuristic method based on a statistical approach for Chinese text segmentation
✍ Christopher C. Yang; K. W. Li 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 251 KB 👁 1 views

## Abstract The authors propose a heuristic method for Chinese automatic text segmentation based on a statistical approach. This method is developed based on statistical information about the association among adjacent characters in Chinese text. Mutual information of bi‐grams and significant estim