0-1 Quadratic programming approach for optimum solutions of two scheduling problems |
| |
| Authors: | BAHRAM ALIDAEE GARY A KOCHENBERGER AHMAD AHMADIAN |
| |
| Affiliation: | 1. Mathematics and Physical Sciences Department , West Texas State University , Canyon, TX, 79016, U.S.A.;2. College of Business Administration , University of Colorado at Denver , Denver, CO, 80217-3364, U.S.A.;3. Management Department , University of Southern Colorado , Pueblo, CO, 81001-4901, U.S.A. |
| |
| Abstract: | Two scheduling problems are considered: (1) scheduling n jobs non-preemptively on a single machine to minimize total weighted earliness and tardiness (WET); (2) scheduling n jobs non-preemptively on two parallel identical processors to minimize weighted mean flow time. In the second problem, a pre-ordering of the jobs is assumed that must be satisfied for any set of jobs scheduled on each specific machine. Both problems are known to be NP-complete. A 0-1 quadratic assignment formulation of the problems is presented. An equivalent 0-1 mixed integer linear programming approach for the problems are considered and a numerical example is given. The formulations presented enable one to use optimal and heuristic available algorithms of 0-1 quadratic assignment for the problems considered here. |
| |
| Keywords: | |
|
|
