MISTA 2005 : Proceedings Contents
Good Neighborhoods and Well-Matched Neighborhoods
Balas E ............................................................................................................2
Seamless Download Scheduling in Computer Networks
Coffman E .........................................................................................................3
Scheduling, a Critical Biography
Lenstra J. K. ......................................................................................................4
Shop Scheduling with Blocking
Brucker P ...........................................................................................................6
Stochastic Scheduling Subject to Preemptive-Repeat Machine
Breakdowns
Cai X ..................................................................................................................6
Hybrid Technologies for Supply Chain Planning and Scheduling
Vazacopoulos A ..................................................................................................6
Constraint Satisfaction
Tsang E ...............................................................................................................6
Supply Chain Scheduling
Hall N .................................................................................................................6
Scheduling in Uncertain and Dynamic Environments
Smith S ...............................................................................................................6
A TSP Formulation of the DNA Sequencing Problem
Nikolakopoulos A and Sarimveis H .....................................................................8
Multi-Criteria Soft Constraints in Timetabling
Rudova H and Vik M ........................................................................................11
Models for Adjacent Resource Scheduling
Duin C. W. and van der Sluis H. J. ....................................................................16
Scheduling Multiple Types of Time-Shared Aircraft: Models and
Methods for Practice
Karaesmen I. Z., Keskinocak P., Tayur S. and Yang W ....................................19
Applications: Abstracts
Systems Design to Scheduling - Open Tools
De Causmaecker P., Demeester P., VandenBerghe G. and Verbeke B. ............40
A Deterministic Scheduling Approach for Wafer Fabrication
Facilities
Mason S. J., Pfund M. and Fowler J. ................................................................42
Multiple Orders Per Job Scheduling Problems
Fowler J., Kutanoglu E. and Mason S. .............................................................44
Optimal Reactive Scheduling for Job Shop, Make-to-order
Industries: A Mould Making Industry Case Study
Gomes M. C., Barbosa-Povoa and Novais A. Q. .............................................46
Multiple Orders Per Job Batch Scheduling on a Single Machine with
Incompatible Jobs
Erramilli V. and Mason S.J. ...............................................................................48
A Decomposition Approach for Batch Scheduling in the Processing
Industry
Maravelias C.T. ...............................................................................................66
How to Maximize Rewards in an Incentived Made-to-order
Scheduling Environment
Glass C. A. and Ng D.S.T. ..............................................................................69
On the Capacitated Packing-Delivering Problem with a Fixed Route
Lei L., Park S. and Liu S. .................................................................................70
Ant Colony Optimisation for Power Plant Maintenance Scheduling
Optimization: A Simplified Hydro Tasmania System
Foong W., Maier H.R. and Simpson A.R. .........................................................72
An Approach to Predictive-reactive Scheduling of Parallel Machines
Subject to Disruptions
Duenas A. and Petrovic D. ...............................................................................74
Approximate Solutions for a New Version of the car Sequencing
Problem
Adenso-Diaz B., Bautista J. and Pereira J. .........................................................93
Random Walks and Neighbourhood Bias in Oversubscribed Scheduling
Roberts M., Whitley L.D., Howe A.E. and Barbulescu L. ..................................98
Tabu Search Algorithms For Cyclic Machine Scheduling Problems
With Blocking
Brucker P. and Kampmeyer T. .......................................................................107
Repair-cost-guided Local Search for Scheduling
Laplagne I., Kwan R.S.K. and Kwan A.S.K. .................................................109
Bicriteria Scheduling of Equal length Jobs with Release Dates on
Identical Parallel Machines
Balasubramanian H., Fowler J. and Keha A. ..................................................112
Enumeration of Pareto Optima for Uniform Parallel Machine
Scheduling with Two Criteria
Bouibede-Hocine K. and T'Kindt V. ..............................................................123
Heuristic Approaches to a Common Due Date Earliness-Tardiness
Scheduling Problem
Gordon V.S. and Tarasevich A.A. .................................................................132
The Single Machine Just-in-time Scheduling Problem with Preemptions
Hendel Y. and Sourd F. .................................................................................140
The single-machine Earliness-tardiness Scheduling Problem with Due
Date Assignment and Resource-dependent Processing Times
Steiner G. and Shabtay D. ..............................................................................149
A Branch-and-bound Algorithm for Single Machine Total Tardiness
Problem with Release Dates
Oguz C. and Yuce E. .....................................................................................162
Large Neighborhood for a Parallel Scheduling Problem with Earliness-
Tardiness Penalties and a Common Due Date
Rios Solis Y.A. and Sourd F. .........................................................................169
A Divide-and merge Algorithm for Single Machine Weighted Tardiness
Problem
Keha A. and Fowler J. ....................................................................................186
Job Shop Scheduling with Earliness, Tardiness and Intermediate
Inventory Holding Costs
Bulbul K. .......................................................................................................188
Scheduling a Single Machine to Minimize a Regular Objective Function
Under Setup Constraints
Pape C.L. and Baptiste P. ...............................................................................193
Efficient Algorithms for Machine Scheduling Problems with Earliness
and Tardiness Penalties
Feng G. and Lau H.C. .....................................................................................196
Stable Single-machine Schedules
Leus R. and Herroelen W. ................................................................................213
Lower Bounds for Parallel Machine Scheduling
Savourey D., Jouglet A. and Baptiste P. .............................................................215
Job Shop Scheduling Problem with Multi-purpose Machines and
Availability Constraints
Zribi N., Kamel A.E. and Borne P. .....................................................................217
Complexity Results for the Parallel Machine Scheduling Problems
with a Server in Computer Systems
Guirchoun S., Souhkal A. and Martineau P. ........................................................232
A Service Level Agreement Protocol and Tabu Search for Scheduling
on Computational Grids
Ouelhadj D., Garibaldi J.M. and Sakellariou R. ..................................................238
How Good are SPT Schedules for Fair Optimality Criteria
Angel E., Bampis E. and Pascual F. ...................................................................244
A Heuristic Algorithm for Scheduling 'Blocked Out' Units in Continuous
Processing Industry: Preliminary Results
Bose S.K. and Bhattacharya S. ..........................................................................258
A Bi-criteria Approach to Scheduling Wafer Fabrication Facilities
Pfund M., Balasubramanian H., Fowler J. and Mason S. ....................................276
Minimizing Makespan with Multiple Orders Per Job in a Two Machine
Flowshop with Item Processing
Laub J. D., Fowler J.W., and Keha A. ...............................................................288
A Sequential Pair Exchange Approach for Solving Single-machine
Scheduling Problems with General Earliness-tardiness Penalties
Lin S-W. and Chou S-Y. ...................................................................................299
Lower and Upper Bounds for the Job-shop Scheduling Problem with
Sequence-dependent Setup Times
Artigues C., Buscaylet F. and Feillet D. ................................................................316
Proactive Resource Allocations Heuristics for Robust Project Scheduling
Braeckmans K., Demeulemeester E. and Herroelen W. ........................................322
Optimal Production Scheduling for Dairy Industries
Doganis P., Sarimveis H., Alexandridis A. and Patrinos P. ....................................324
Approximations to Optimal k-unit Cycles for Dual Gipper Robot Cells
Geismar H.N., Dawande M. and Sriskandaranjah C. ............................................326
The Unit-Operation-Stock Superstructure (UOSS) and the
Quality-Logic-Quality Paradigm (QKQP) for Production Scheduling in
The Process Industries
Kelly J.D. ............................................................................................................327
Forming and Scheduling Jobs with Order Weights in Semiconductor
Manufacturing
Tanrisever F. and Kutanoglu E. ............................................................................334
A Tabu-Search Based Reactive Procedure for the RCPSP with
Stochastic Resource Availabilities
Lambrechts O., Demeulemeester E. and Herroelen W. .........................................335
A Survey on Minimizing Makespan for the Preemptive job shop with
Two Machines
Kimbrel T. ...........................................................................................................337
Single Machine Product Scheduling with Outsourcing Allowed
Sung C.S., Lee I.S., Yoon S.H. and Juhn J.H. .......................................................340
An Evaluation of Exact and Suboptimal Procedures for Constructing
Stable Project Schedules
Van de Vonder S., Demeulemeester E. and Herroelen W. ......................................341
Periodic Real-time Scheduling: From Latency-based Model to
Deadline-based Model
Cucu L. and Sorel Y. .............................................................................................344
A Comparison of Combinatorial Optimization and Dispatch Rules for
Online Scheduling
Montana D. ...........................................................................................................353
Job Shop Scheduling with Log-sizing and Batching in an Uncertain
Real-world Environment
Petrovic S., Fayad C and Petrovic D. ....................................................................363
A History of Decision-Making Tools for Production Scheduling
Herrmann J. W. .....................................................................................................380
Challenges in Matching Assets with Demand across All Supply
Chain Management Decision Tiers in the IBM Microelectronics
Division from Automation Fabs to Central Planning Engines to
Collaborative Behaviour (Work Around)
Fordyce K., Burda R., Degbotse A., Milne J., Morrison J. R. and
Williamson E. ...........................................................................................................391
Scheduling Wafer Fabrication Operations: State-of-the-practice
And Future Needs
Fowler J. and Pfund M. .............................................................................................392
Scheduling Product Families in a High Volume, Flexible,
Assemble-to-order Factory
Monkman S. K., Morrice D. J. and Bard J. F. ............................................................394
A Decomposition, Construction and Post-processing Approach
For Nurse Rostering
Brucker P., Qu R., Burke E. and Post G. ...................................................................397
Integrating Nurse and Surgery Scheduling
Belien J. and Demeulemeester E. .................................................................................408
An Electromagnetic Meta-heuristic for the Nurse Scheduling
Problem
Maenhout B. and Vanhoucke M. ..................................................................................410
An Investigation of Variable Neighbourhood Search for the
University Course Timetabling
Abdullah S., Burke E. K. and McCollum B. ...................................................................413
A Zero-Inventory Production-Distribution Problem with
Time-Window Constraints
Armstrong R., Lei L. and Gao S. ....................................................................................428
Scheduling UET-UCT Task Systems under the Out-forest
Precedence Constraints
Hanen C. and Zinder Y. ..................................................................................................445
The Worst-case Analysis of the Garey-Johnson Algorithm for
Preemptive Tasks on m Processors
Hanen . and Zinder Y. .....................................................................................................453
Scheduling Orders in Dedicated and Flexible Machine Environments
Leung J. Y. T., Li H. and Pinedo M. .................................................................................471
Retractable Contract Network for Distributed Scheduling
Tsang E. P. K., Gosling T., Virginas B., Voudouris C. and Owusu G. ................................485
Scheduling Algorithms for Master-slave Systems
Leung J. Y. T. and Zhao H. ...............................................................................................501
Search Algorithms: Abstracts
Skills-Based Agent Scheduling at Call Centres
Aykin T. and McKenna J. S. .............................................................................................515
Timetable Synchronization for Mass Transit
Leung J. M. Y. and Wong R. C. W. ..................................................................................516
Algorithms for Online Buffer Management
Mahdian M., Bansal N., Fleischer L. K., Kimbrel T.,
Schieber B. and Svirdenko M. ..........................................................................................518
A Practitioner's Approach to Distribution and Supply Chain
Planning and Management
Miller T .............................................................................................................................519
Job Shop Scheduling with Set-up Times, Deadlines and
Precedence Constraints
Balas E., Simonetti N. and Vazacopoulos A. .....................................................................520
Worst-case Analysis for Queueing Service Policies
Wang Z. and Xing W. .......................................................................................................533
Integrated Scheduling of Different Types of Handling Equipment
At Automated Container Terminals
Lau H. Y. K., Zhao Y. and Pan C. ....................................................................................536
Single Machine Multiple Orders Per Job Scheduling Using
Column Generation
Jampani J., Mason S. J. and Erramilli V. .............................................................................539
Integrated Production-distribution Scheduling to Optimize the
Trade off between Order Delivery Performance and Total Cost
Pundoor G. and Chen Z-L. .................................................................................................549
Combined Production and Distribution Scheduling of Ready-mix
Concrete
Fong P. Y. and Piplani R. ....................................................................................................551
Incremental Propagation Rules for a Precedence Graph with
Optional Activities and Time Windows
Bartak R. and Cepek O. ......................................................................................................552
Scheduling on a Single Machine to Minimize Total Flow Time
With Job Rejections
Bunde D. P. .........................................................................................................................562
Online Scheduling of Precedence Constrained Tasks
Huo Y. and Leung J. Y-T. ....................................................................................................573
Bicriteria Parallel Task Scheduling
Baille F., Bampis E., Laforest C. and Rapine C. ....................................................................585
On Project Scheduling with and/or Precedence Constraints
Adelson-Velsky G., Gelbukh A and Levner E. ......................................................................597
New Tight NP-hardness of Preemptive Multiprocessor and Open
Shop Scheduling
Shchepin E., and Vakhania N. ..............................................................................................606
Single-machine Scheduling with General Costs under Compound-type
Distributions
Cai X., Wu X., and Zhou X. .................................................................................................630
A Comparison of Different Formulations for the Non-preemptive
Single Machine Total Weighted Tardiness Scheduling Problem
Khowala K., Keha A and Fowler J. ......................................................................................643
On the Complexity of Adjacent Resource Scheduling
Duin C. and van der Sluis H. J. ..............................................................................................653
Improved Approximation Algorithms for Broadcast Scheduling
Bansal N., Coppersmith D. and Sviridenko M. .......................................................................655
Graphical Tools for Heuristic Visualization
Ranson D. and Cheng P. C-H. ...............................................................................................658
Course Timetabling - Extended Tiles for University Timetabling
Adriaen M., De Causemaecker P. and Vanden Berghe G. ......................................................669
A Predictive-reactive Approach for RCPSP with Labour
Constraints and Time-dependent Activities Requirements
Drezet L-E., and Billaut J-C. ...................................................................................................671
Solving a Timetabling Problem using Bender's Decomposition
Sarin S. C., Wang Y., and Varadarajan A. ..............................................................................673
Applying the Extended Network Simplex Algorithm to Dynamic
Automated Guided Vehicles Scheduling
Rashidi H. and Tsang E. P. K. .................................................................................................677
Transport Scheduling: Abstracts
On a Certain Berth Scheduling Problem
Blazewicz J., Machowiak M., Cheng T. C. E. and Oguz C. .....................................................694
Forecasting Flight Schedule Robustness
Burke E., DeCausemaecker P., DeMaere G., Mulder J. and Paelinck M. ................................698
Scheduling the Production and Transportation Operations subject
To Dynamic Arrivals
Fan C., Kumar M., Lei L., and Yang J. ...................................................................................701
Building Robustness into Train Driver Schedules
Kwan A. S. K., Laplagne I. and Kwan R. S. K. ......................................................................702
Improved Pruning in Column Generation of a Vehicle Routing
Problem
Westphal S. and Krumke S. O. ................................................................................................705
Vehicle Routing and Scheduling with Time Varying Travel Times
Eglese R. and Maden W. ..........................................................................................................724
A Dynamic Programming Approach to the Truckload Routing
Problem using a Triplet Formulation
Miori V. M. ..............................................................................................................................725
Inventory Control and Scheduling with Facilities in Parallel
Krasik V., Leung J., Pinedo M. and Zhang J. .............................................................................740
Analytic Evaluation of the Expectation and Variance of Different
Performance Measures for Scheduling Jobs on a Single
Machine under Processing Time Variability
Sarin S. and Nagarajan B. ........................................................................................................744
A Genetic Algorithm with Random Keys Approach for the Job
Shop Scheduling Problem with Earliness and Tardiness
Bedoya-Valencia L., Rodriguez-Velasquez E. and Rabadi G. .....................................................745