# SESSION A7: GOTHA: Applied Models for Scheduling Problems

## [200] A branch and bound
algorithm for one supplier and multiple heterogeneous
customers to solve a coordinated scheduling problem

Hammoudan Zakaria, Olivier Grunder, Toufik Boudouh and
Abdellah El Moudni

Considerable attention had previously been given to the single-vendor single-customer integrated inventory problem, but there had been very little work on the integrated single-vendor multi-customer and multi-product consideration. Here, we develop a generalized single-vendor multi-customer with multi-product consideration supply chain model with one transporter available to deliver the products from the supplier to the customers. The objective is to solve the proposed model and to find the minimized total cost, while guaranteeing a certain customer service level. A mathematical formulation of the problem is given in a general way. Then, we propose a branch and bound algorithm as an exact method and an efficient heuristic greedy algorithm. Both procedures are then compared through computational experiments which show that the heuristic algorithm is capable of generating near-optimal solutions within a short amount of CPU time.

## [241] An effective
iterative lower bound algorithm for the single machine
scheduling problem with unavailability constraint and
release date jobs and tails for maximum lateness
minimization

Hfaiedh Walid, Chérif Sadfi, Kacem Imed and B. Hadj-Alouane Atidel

We consider the single machine scheduling problem with release date and delivery time jobs where the machine is unavailable during a known period, named hole. The problem is strongly NP-hard even in the case without unavailability period. We present in this paper a comparison study of an extension of Schrage algorithm as an upper bound and Jackson Preemptive Schedule as a lower bound. Then, we propose an improvement lower bound which is based on iterative procedure. Computational results are provided to show the efficiency of the approach.

## [219] On the single-processor
scheduling problem with time restrictions

Rachid Benmansour, Oliver Braun and Abdelhakim Artiba

This paper presents a time-indexed mixed integer programming formulation for the single-processor scheduling problem with time restrictions that has been formulated at first by Braun et al. in [1]. The problem is as follows. A set of n independent jobs are simultaneously available for processing at the beginning of the planning horizon, and their processing times are fixed and known in advance. The jobs have to be processed non-preemptively on a single processor that can handle only one job at a time. Furthermore, during any time period of length *a* > 0 the number of jobs being executed is less than or equal to a given integer value *B* >= 2. The objective is to minimize the completion time of the last job in the optimal sequence (i.e. the makespan). To our knowledge, this is the first time that a mathematical model is given to solve the single processor scheduling problem with time restrictions exactly. The performance of the model is tested by running it on randomly generated instances. The computational analysis shows that the proposed model, without any valid cuts, performs considerably well for small instances and a relatively large value of the integer *B*.

## [213] A Bi-objective
optimization model for single-machine batch scheduling
considering energy cost

Junheng Cheng, Feng Chu, Weili Xia, Jianxun Ding and Xiang Ling

Electricity is one of most widely used energies and encouraged to be saved by scientific management and new technologies such as Time-of-Use policy. Batch scheduling can significantly improve production efficiency and is used in many high electricity consumption and high technology industries. This paper investigates a new bi-objective single machine batch scheduling problem with TOU policy. The first objective is to improve productivity and the second aims to minimize the total electricity cost. For the problem, a bi-objective mixed integer nonlinear programming model is formulated. Its corresponding single objective optimization problems are linearized by analyzed properties such that the multiobjective ε-constraint method can be used to obtain Pareto solutions.