Multilevel refinement for combinatorial optimisation problems

We consider the multilevel paradigm and its potential to aid the solution of combinatorial optimisation problems. The multilevel paradigm is a simple one, which involves recursive coarsening to create a hierarchy of approximations to the original problem. An initial solution is found (sometimes for the original problem, sometimes the coarsest) and then iteratively refined at each level. As a general solution strategy, the multilevel paradigm has been in use for many years and has been applied to many problem areas (most notably in the form of multigrid techniques). However, with the exception of the graph partitioning problem, multilevel techniques have not been widely applied to combinatorial optimisation problems. In this paper we address the issue of multilevel refinement for such problems and, with the aid of examples and results in graph partitioning, graph colouring and the travelling salesman problem, make a case for its use as a metaheuristic. The results provide compelling evidence that, although the multilevel framework cannot be considered as a panacea for combinatorial problems, it can provide an extremely useful addition to the combinatorial optimisation toolkit. We also give a possible explanation for the underlying process and extract some generic guidelines for its future use on other combinatorial problems.

Single machine scheduling and due date assignment under series-parallel precedence constraints

We consider a single machine due date assignment and scheduling problem of minimizing holding costs with no tardy jobs tinder series parallel and somewhat wider class of precedence constraints as well as the properties of series-parallel graphs.

Two-machine flow shop scheduling problems with no-wait jobs

In this paper we provide a fairly complete complexity classification of various versions of the two-machine permutation flow shop scheduling problem to minimize the makespan in which some of the jobs have to be processed with no-wait in process. For some version, we offer a fully polynomial-time approximation scheme and a 43-approximation algorithm.

Approximation results for flow shop scheduling problems with machine availability constraints

This paper considers two-machine flow shop scheduling problems with machine availability constraints. When the processing of a job is interrupted by an unavailability period of a machine, we consider both the resumable scenario in which the processing can be resumed when the machine next becomes available, and the semi-resumable scenario in which some portion of the processing is repeated but the job is otherwise resumable. For the problem with several non-availability intervals on the first machine under the resumable scenario, we present a fast (3/2)-approximation algorithm. For the problem with one non-availability interval under the semi-resumable scenario, a polynomial-time approximation scheme is developed.

Operator non-availability periods

In the scheduling literature, the notion of machine non availability periods is well known, for instance for maintenance. In our case of planning chemical experiments, we have special periods (the week-ends, holidays, vacations) where the chemists are not available. However, human intervention by the chemists is required to handle the starting and termination of the experiments. This gives rise to a new type of scheduling problems, namely problems of finding schedules that respect the operator non availability periods. These problems are analyzed on a single machine with the makespan as criterion. Properties are described and performance ratios are given for list scheduling and other polynomial-time algorithms.

Learning and practising supply chain management strategies from a business simulation game: a comprehensive supply chain simulation

An Internet based supply chain simulation game (ISCS) is introduced and demonstrated in this paper. Different from other games and extended from the Beer Game, a comprehensive set of supply chain (SC) management strategies can be tested in the game, and these strategies can be evaluated and appraised based on the built-in Management Information System (MIS). The key functionalities of ISCS are designed to increase players SC awareness, facilitate understanding on various SC strategies and challenges, foster collaboration between partners, and improve problem solving skills. It is concluded that an ISCS can be used as an efficient and effective teaching tool as well as a research tool in operations research and management science. Problems and obstacles have been observed while engaging in the SC business scenario game. The actions proposed and implemented to solve these problems have resulted in improved SC performance.