Shop-scheduling problems with fixed and non-fixed machine orders of the jobs

The paper deals with the determination of an optimal schedule for the so-called mixed shop problem when the makespan has to be minimized. In such a problem, some jobs have fixed machine orders (as in the job-shop), while the operations of the other jobs may be processed in arbitrary order (as in the open-shop). We prove binary NP-hardness of the preemptive problem with three machines and three jobs (two jobs have fixed machine orders and one may have an arbitrary machine order). We answer all other remaining open questions on the complexity status of mixed-shop problems with the makespan criterion by presenting different polynomial and pseudopolynomial algorithms.

The use of evacuation modelling techniques in the design of very large transport aircraft and blended wing body aircraft

Very Large Transport Aircraft (VLTA) pose considerable challenges to designers, operators and certification authorities. Questions concerning seating arrangement, nature and design of recreational space, the number, design and location of internal staircases, the number of cabin crew required and the nature of the cabin crew emergency procedures are just some of the issues that need to be addressed. Other more radical concepts such as blended wing body (BWB) design, involving one or two decks with possibly four or more aisles offer even greater challenges. Can the largest exits currently available cope with passenger flow arising from four or five aisles? Do we need to consider new concepts in exit design? Should the main aisles be made wider to accommodate more passengers? In this paper we demonstrate how computer based evacuation models can be used to investigate these issues through examination of staircase evacuation procedures for VLTA and aisle/exit configuration for BWB cabin layouts.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.