Search

This paper addresses the minimal makespan parallel machine problem where machines are subject to preventive maintenance events of a known deterministic duration. The processing time of a job depends on its predecessors since the machine’s last maintenance. The paper proposes some dominance criteria for sequences of jobs assigned to a machine, and uses these criteria to design constructive heuristics to this NP-hard problem. The computational investigation determines the parameters that make a hard instance and studies the sensitivity of the heuristics to these parameters.

The D-minimax criterion for estimating slopes of a response surface involving k factors is considered for situations where the experimental region χ and the region of interest ℜ are co-centered cubes but not necessarily identical. Taking χ = [ − 1, 1]k and ℜ = [ − R, R]k, optimal designs under the criterion for the full second-order model are derived for various values of R and their relative performances investigated. The asymptotically optimal design as R → ∞ is also derived and investigated. In addition, the optimal designs within the class of product designs are obtained. In the asymptotic case it is found that the optimal product design is given by a solution of a cubic equation that reduces to a quadratic equation for k = 3 and 6. Relative performances of various designs obtained are examined. In particular, the optimal asymptotic product design and the traditional D-optimal design are compared and it is found that the former performs very well.

This paper addresses the problem of scheduling on-time jobs on unrelated parallel machines with machine production costs. The objective is to maximise the net profit which is the sum of the weights of on-time jobs and the cost of using the machines. This scheduling problem is very important and frequent in industrial settings. It is herein solved using an exact approach that applies Benders decomposition to obtain tight upper and lower bounds and uses the bounds within a branch and bound. The computational investigation shows the efficacy of the approach in solving large instances. Most importantly, the proposed approach provides a new venue for solving large-scale scheduling problems.

This paper considers the minimal earliness tardiness -machine permutation flow shop scheduling problem with distinct due dates and no inserted idle time when a job is waiting. It models the problem as a mixed integer program, and approximately solves it using , a fast variable neighborhood based hybrid heuristic. is an iterated local search that applies a variable neighborhood descent as its search engine. The numerical testing provides computational proof of the good performance of , which matches existing upper bounds of 20.02% benchmark instances and tightens 70.54% ones with an average percent deviation from the best upper bound of 0.07%.

Scheduling jobs with different processing times and distinct known due dates on parallel machines (which may be idle) so as to minimise the total weighted earliness and tardiness is NP-hard. It occurs frequently in industrial settings with a just-in-time production environment. Here, small instances of this problem are tackled via an exact mixed-integer program, whereas larger instances are approximately solved using hybrid algorithms. The computational investigation discerns what makes a difficult instance, and demonstrates the efficiency of the approach.