| In this dissertation, we consider manufacturing and service environments, where the due dates are 100% reliable, i.e. the customer will be delivered the requested service or product on its due date (if the order is accepted). We consider two types of situations. In the first case, the due dates are set by the customer, all the orders have to be accepted and the customer demand must be satisfied on time, possibly by subcontracting. In the second case, when a customer demand arrives, the manufacturer will quote a due date and once the due date is quoted, the order must be delivered before this quoted due date (but an order may be rejected).; The first model we consider was motivated by an application from the airline industry: scheduling of time-shared jet aircraft. At any time, the aircraft are at different locations or serving a customer, and new customer requests arrive, each consisting of a departure location, departure time and destination. All customer requests must be satisfied (by sub-contracting extra aircraft if necessary), under additional constraints of maintenance requirements of the aircraft and previously scheduled trips. Our goal is to find a feasible schedule for the flights of aircraft, so that the operational expenses and the cost of subcontracting is minimized. The algorithms we developed for this model are currently being used by a company.; In the second model, there is a single serve and customers arrive over time. Associated with each customer, there is a unit revenue {dollar}wsb{lcub}i{rcub}{dollar}, a processing time {dollar}psb{lcub}i{rcub}{dollar} and a maximum lead time {dollar}lsb{lcub}i{rcub},{dollar} such that if the manufacturer does not promise to start the processing of order i within {dollar}lsb{lcub}i{rcub}{dollar} time units after its arrival, the customer will not place the order (or the order is rejected). We assume that if we accept an order i and quote a lead time {dollar}dsb{lcub}i{rcub},{dollar} then the revenue for this order is going to be {dollar}wsb{lcub}i{rcub}(lsb{lcub}i{rcub}-dsb{lcub}i{rcub}){dollar} for {dollar}dsb{lcub}i{rcub} |
